← 返回题目列表

Codeforces · 2205/D

D. 西蒙斯和击败峰

中文机器翻译题面 查看原题

我最美好的愿望消散在空气中;十八岁时,我把自己的梦想倾注在麦克风里与大家分享。
— 顺, 720

我们称长度为 $$$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 执行的最小操作数。

示例

输入
复制

5
3
1 2 3
5
4 1 3 2 5
6
4 5 3 6 2 1
7
6 5 1 7 4 2 3
15
7 4 10 12 9 14 5 3 8 11 1 15 2 13 6

输出
复制

0
1
3
3
9

注意

在第一个测试用例中,数组是 酷 最初,所以西蒙斯无法执行任何操作。答案是$$$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$$$ 操作中。