题目描述

Sashka 正在给保加利亚国家队拍合影。当前照片中有 $N$ 个人，从左到右第 $i$ 个人的身高为 $a_i$。

若一个人位于中间位置 $i$，即 $1<i<N$，并且满足

则称这个人是一个“药瓶”。Sashka 可以让任意一个当前是“药瓶”的人离开照片。若第 $i$ 个人离开，左右两边的人会靠拢，身高序列变为

例如，若序列为 $\{1,3,6,9,4\}$，可以让身高为 $6$ 的人离开，此后序列变为 $\{1,3,9,4\}$。

Sashka 希望尽可能多的人离开照片。对于每个给定的身高序列，求最终照片中最少可以剩下多少人。

输入格式

第一行一个整数 $T$，表示测试组数。

接下来每组数据包含两行：

第一行一个整数 $N$。
第二行 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出格式

对于每组数据，输出一行一个整数，表示最终最少剩下的人数。

数据范围

• $1\le T\le 1000$；
• $3\le N$；
• 所有测试组的 $\sum N\le 300000$；
• $1\le a_i\le 10^9$。

子任务

只有通过某个子任务的所有测试点，才能获得该子任务分数。

样例

输入

3
5
1 2 3 4 5
7
1 3 5 6 7 8 10
3
1 1 1

输出

2
4
2