06772. USACO·奶牛合影 未做

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

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

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

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

你需要回答多个测试用例。

输入的第一行包含一个整数 $T$（$1\le T\le 10^5$），为测试用例的数量。以下为 $T$ 个测试用例。

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

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

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

【样例解释】

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

• 测试点 4-5：$T\le 10^4$，所有奶牛的身高不超过 10。

• 测试点 6-11：没有额外限制。

【数据规模与约定】

• 测试点 2-3：$T\le 100$，$N\le 7$。

• 测试点 4-5：$T\le 10^4$，所有奶牛的身高不超过 10。

• 测试点 6-11：没有额外限制。

供题：Nick Wu