题目内容

Tk有一个魔法藤蔓，这个藤蔓有 $n$ 个魔法段，这个魔法藤蔓从头到尾均有一个魔法硬度 $\{a_1,a_2,\dots,a_n\}$，Tk 想要进行一定以下操作（每次二选一），直到开头的那一段被剪掉：

• 选择选择剩余藤蔓中魔法硬度最高的魔法段（如果有多个满足条件的只能选择距离开头最远的一个魔法段），将此魔法段及其后面的魔法段剪掉。
• 选择选择剩余藤蔓中魔法硬度最低的魔法段（如果有多个满足条件的只能选择距离开头最远的一个魔法段），将此魔法段及其后面的魔法段剪掉。

Tk 想知道满足条件最少要操作多少次。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ $(1 \le T \le 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n$ $(1 \le n \le 2 \times 10^5)$ 表示魔法段数。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ $(1 \le a_i \le 10^5)$ 表示每段魔法段的魔法硬度。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$。

输出描述

对于每一组测试数据，新起一行，输出一个整数表示最小操作次数。

样例1

输入

2
3
1 3 2
4
4 2 4 1

输出

1
2