题目背景

原题为 P12023 [USACO25OPEN] More Cow Photos B

题目描述

今天同学们特别顽皮！Gooby 只是想拍摄一张同学们排成一行的照片，但同学们总是在他得到机会按下快门之前移动位置。

具体地说，Gooby 的 $N$ 个学生（$1 \le N \le 10^5$）每一个的身高都是 $1$ 到 $N$ 的整数。Gooby 想让同学们以一种特定的顺序排成一行后再拍照片。如果同学们排成一行时从左到右有身高 $h_1, \dots, h_K$，他希望同学们的身高拥有以下三个性质：

• 他希望同学们的身高先递增再递减。形式化地说，必须存在一个整数 $i$ 使得 $h_1 \le \dots \le h_i \ge \dots \ge h_K$。
• 他不希望任何同学与另一个身高完全相同的同学相邻。形式化地说，对于所有 $1 \le i < K$ 有 $h_i \neq h_{i+1}$。
• 他希望照片是对称的。形式化地说，如果 $i + j = K+1$，则 $h_i = h_j$。

Gooby 希望照片中包含尽可能多的同学。具体地说，Gooby 可以移除一些同学并重新排列余下的同学。计算 Gooby 在满足他的限制的情况下可以在照片中包含的同学的最大数量。

输入格式

你需要回答多个测试用例。 输入的第一行包含一个整数 $T$（$1 \leq T \leq 10^5$），为测试用例的数量。以下为 $T$ 个测试用例。

每一个测试用例的第一行包含一个整数 $N$。第二行包含 $N$ 个整数，为可用的 $N$ 个同学的身高。同学们的身高在 $1$ 到 $N$ 之间。

输入保证所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。每行包含一个整数，表示 Gooby 可以在照片中包含的同学的最大数量。

输入输出样例 #1

输入 #1

2
4
1 1 2 3
4
3 3 2 1

输出 #1

3
1

说明/提示

对于第一个测试用例，Gooby 可以选择身高为 $1$，$1$ 和 $3$ 的同学，并重新排列为 $[1,3,1]$，满足所有条件。对于第二个测试用例，Gooby 可以选择身高为 $3$ 的同学以组成一张合法的照片。

• 测试点 $1\sim2$：$T\le 100$，$N \le 7$。
• 测试点 $3\sim4$：$T \le 10^4$，所有同学的身高不超过 $10$。
• 测试点 $5\sim10$：没有额外限制。