Home Web Board ProblemSet Standing Status Statistics
1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!
Problem H: Perfect formation

Problem H: Perfect formation

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 9  Solved: 1
[Submit][Status][Web Board]

Description

Nick came up with a new perfect formation game!
Let's say that there are n people standing in front of him in order, and their heights are h [1], h [2]... H [n], nick hopes to pick out some of them to form a new formation. If the new formation meets the following three requirements, it will be the new perfect formation:
1. The selected person maintains the relative order of the original formation, and must be continuous in the original formation;
2. left and right sides is symmetrical, suppose there are m individuals to form a new formation, the individual and the 1st people's height and ther m th people's height is the same, the same height for individuals and the 2nd man and the m - 1th man, and so on, of course, if m is odd, the middle one can arbitrarily;
3. From left to middle of the person, height needs to be guaranteed not to decline. If H represents the height of the new formation, then H [1] < = H [2] < = H [3]... < = H [mid].Now nick wants to know: how many people can be chosen to make up the new perfect formation?

Input


The first line of input data contains an integer T, indicating that there is a total of T group test data (T < = 20),T is several test cases;
Each group of data in the first place is an integer n (1 < = n < = 100000), said the number of original formation, the next line of the input n integers, said the original faormation from left to right standing height ( 50< = h < = 250, does not exclude the special small and large).

Output

Please print the maximum number of lines that make up the perfect formation.

Sample Input

2
3
51 52 51
4
51 52 52 51

Sample Output

3
4

HINT

[Submit][Status][Web Board]