#OJ1523. Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。 具体而言,栋栋的花的高度可以看成一列整数h1, h2,… ,hn。设当一部分花被移走后, 剩下的花的高度依次为g1,g2,...,gm,则栋栋希望下面两个条件中至少有一个满足: 条件 A:对于所有的1≤i≤m/2,有g2i>g2i-1,同时对于所有的1≤i≤m/2,有g2i>g2i+1; 条件 B:对于所有的1≤i≤m/2,有g2i< g2i-1,同时对于所有的1≤i≤m/2,有g2i < g2i+1; 注意上面两个条件在m = 1时同时满足,当m > 1时最多有一个能满足。 请问,栋栋最多能将多少株花留在原地。

Input

多组测试数据。输入第一行一个数T<=20,表示测试数据组数。 每组测试数据输入的第一行包含一个整数n,表示开始时花的株数。第二行包含n个整数,依次为h1, h2, … , hn,表示每株花的高度。数据范围:1 ≤ n ≤ 100,000,0 ≤ hi ≤ 1,000,000。

Output

输出共T行,每行对应一组测试数据。每行包含一个整数m,表示最多能留在原地的花的株数。

Sample Input

1
5
5 3 2 1 2

Sample Output

3

HINT

Append Code