bronze_More_Cow_Photos (USACO US_Open_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: ad-hoc

The cows are in a particularly mischievous mood today!  All Farmer John wants to
do is take a photograph of the cows standing in a line, but they keep moving
right before he has a chance to snap the picture.
Specifically, each of FJ's $N$ cows $(1 \le N \le 10^5)$ has an integer height
from $1$ to $N$. FJ wants to take a picture of the cows standing in line in a
very specific ordering. If the cows have heights $h_1, \dots, h_K$ when lined up
from left to right, he wants the cow heights to have the following three
properties:
He wants the cow heights to increase and then decrease. Formally, there must
exist an integer $i$ such that $h_1 \le \dots \le h_i \ge \dots \ge h_K$.
He does not want any cow standing next to another cow with exactly the same
height. Formally, $h_i \neq h_{i+1}$ for all $1 \le i < K$.
He wants
the picture to be symmetric. Formally, if $i + j = K+1$, then $h_i = h_j$.
FJ wants the picture to contain as many cows as possible. Specifically, FJ can
remove some cows and rearrange the remaining ones. Compute the maximum number of
cows FJ can have in the picture satisfying his constraints.
INPUT FORMAT (input arrives from the terminal / stdin):
You have to answer multiple test cases.
The first line of input contains a single integer $T$ ($1 \leq T \leq 10^5$)
denoting the number of test cases. $T$ test cases follow.
The first line of every test case contains a single integer $N$. The second line
of every test case contains $N$ integers, the heights of the $N$ cows available.
The cow heights will be between $1$ and $N$.
It is guaranteed the sum of $N$ over all test cases will not exceed $10^6$.
OUTPUT FORMAT (print output to the terminal / stdout):
Output $T$ lines, the $i$'th line containing the answer to the $i$'th test case.
Each line should be an integer denoting the maximum number of cows FJ can
include in the picture.
SAMPLE INPUT:
2
4
1 1 2 3
4
3 3 2 1
SAMPLE OUTPUT:
3
1
For the first test case, FJ can take the cows with heights $1$, $1$, and $3$,
and rearrange them into $[1,3,1]$, which satisfies all the conditions. For the
second test case, FJ can take the cow with height $3$ and form a valid photo.
SCORING:
Inputs 2-3: $T\le 100, N \le 7$
Inputs 4-5: $T \le 10^4$, all cows will have height at most 10.
Inputs 6-11: No additional constraints.
Problem credits: Nick Wu

Starter code:

Grader code:

Setup script:

Evaluation script: