题目内容

仓库中从前到后依次排列着 n 个货架，第 $i$ 个货架的存货量为整数 $a_i$。你需要反复执行下列两种操作之一，直到最前面的货架也被清掉为止：

• 在当前仍保留的货架中，选出存货量最大的一个；若有多个，只能选距离最前端最远的那个。将该货架及其后面的所有货架一并清掉。
• 在当前仍保留的货架中，选出存货量最小的一个；若有多个，只能选距离最前端最远的那个。将该货架及其后面的所有货架一并清掉。 求最少需要执行多少次操作。数据范围：测试组数 $T$ 满足 $1 \le T \le 10^4$；每组中 $1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^5$；单个测试文件中所有 n 之和不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 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

输入

3
1
5
5
2 5 3 5 1
2
7 7

输出

1
2
2

说明

设 $dp[i]$ 表示清掉前 $i$ 个货架的最少次数。对前缀 $[1,i]$，记存货量最大值最靠后的下标为 $maxPos$，最小值最靠后的下标为 $minPos$，则 $dp[i]=1+\min(dp[maxPos-1],dp[minPos-1])$。

第一组：只有一个货架，操作一次即可清掉，答案为 1。

第二组：$a=[2,5,3,5,1]$。整段最靠后的最大值在第 4 位，最靠后的最小值在第 5 位，$dp[5]=1+\min(dp[3],dp[4])=2$。

第三组：两个货架存货量相同，最大值与最小值都取最靠后的第 2 位，$dp[2]=1+dp[1]=2$。

样例2

输入

1
6
3 1 4 1 5 9

输出

3

说明

存货量为 $3,1,4,1,5,9$。从左到右更新最靠后的极值位置后得到：$dp[1]=1$，$dp[2]=1$，$dp[3]=2$，$dp[4]=2$，$dp[5]=3$，$dp[6]=3$。

整段最大值在末尾第 6 位，最小值在第 4 位，因此 $dp[6]=1+\min(dp[5],dp[3])=3$。

样例3

输入

2
5
9 8 7 6 5
4
4 4 4 4

输出

1
4

说明

第一组：存货量严格递减，全局最大值就在最前端。选择最大值会把全部货架一次性清掉，答案为 1。

第二组：四个货架存货量全部相同，每次极值都取当前前缀的最右端，于是 $dp[i]=i$，答案为 4。