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]


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?


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).


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

Sample Input

51 52 51
51 52 52 51

Sample Output



[Submit][Status][Web Board]