我们称长度为 $$$m$$$ 的数组为 $$$b$$$ 酷 当且仅当:
- 存在 no 索引 $$$i$$$ ($$$1 \lt i \lt m$$$) 使得 $$$b_i=\max(\{b_{i-1}, b_i, b_{i+1}\})$$$。
Simons 有一个大小为 $$$n$$$ 的数组 $$$a$$$。最初,该数组是一个排列$$$^{\text{*}}$$$。
他必须执行以下操作,直到数组被 酷:
- 选择索引 $$$i$$$ ($$$1 \lt i \lt n$$$) 使得 $$$a_i=\max(\{a_{i-1}, a_i, a_{i+1}\})$$$。
- 然后,他可以删除 $$$a_{i-1}$$$ or $$$a_{i+1}$$$ 来自数组。移除后,数组中出现间隙,间隙的左右两侧会重新接合。
求 Simons 执行的最少操作数。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5\cdot 10^4$$$)。测试用例的描述如下。
第一行包含一个整数 $$$n$$$ ($$$3\le n\le 5\cdot 10^5$$$) — $$$a$$$ 的大小。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$,所有 $$$a_i$$$-s 都是不同的) - Simons 最初的数组。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - Simons 执行的最小操作数。
示例
输入复制
531 2 354 1 3 2 564 5 3 6 2 176 5 1 7 4 2 3157 4 10 12 9 14 5 3 8 11 1 15 2 13 6
输出复制
01339
注意
在第一个测试用例中,数组是 酷 最初,所以西蒙斯无法执行任何操作。答案是$$$0$$$。
在第二个测试用例中,Simons 可以执行如下操作:
- 选择索引 $$$3$$$,因为 $$$a_3=\max(\{a_2,a_3,a_4\})$$$。然后,他从数组中删除 $$$a_{2}$$$。该数组变为$$$[4,3,2,5]$$$。
我们可以看到数组是 酷 现在。因此,答案是$$$1$$$。
在第三个测试用例中,Simons 可以执行如下操作:
- 选择索引 $$$2$$$。然后,他从数组中删除 $$$a_1$$$。该数组变为 $$$[5,3,6,2,1]$$$。
- 选择索引 $$$3$$$。然后,他从数组中删除 $$$a_2$$$。该数组变为$$$[5,6,2,1]$$$。
- 选择索引 $$$2$$$。然后,他从数组中删除 $$$a_1$$$。该数组变为 $$$[6,2,1]$$$。
因此,西蒙斯制作了数组 酷 在 $$$3$$$ 操作中。