CF2205D Simons and Beating Peaks

我最美好的愿望随风消散；十八岁时，我将梦想倾注于麦克风，与你们分享。 —— SHUN，[720](https://open.spotify.com/track/3bhQrFuaaPk8pMMb7TcU2d) 我们称长度为 $m$ 的数组 $b$ 为“cool”（酷），当且仅当： - 不存在下标 $i$（$1 < i < m$），使得 $b_i = \max(\{b_{i-1}, b_i, b_{i+1}\})$。 Simons 有一个大小为 $n$ 的数组 $a$。最初，该数组是一个排列$^{\text{∗}}$。 他需要持续进行如下操作，直到数组变为cool： - 选择一个下标 $i$（$1 < i < n$），满足 $a_i = \max(\{a_{i-1}, a_i, a_{i+1}\})$。 - 然后，他可以从数组中删除 $a_{i-1}$ 或 $a_{i+1}$。删除后，数组的左右部分会重新拼接起来形成一个新数组。 请你求出 Simons 至少需要进行多少次操作。 $^{\text{∗}}$ 长度为 $n$ 的排列是指一个包含 $1$ 到 $n$、且每个数恰好出现一次的数组。比如 $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，但出现了 $4$）。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \leq t \leq 5 \cdot 10^4$）。接下来描述各组测试数据。 第一行包含一个整数 $n$（$3 \leq n \leq 5 \cdot 10^5$）——$a$ 的长度。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq n$，且所有 $a_i$ 都互不相同），表示 Simons 最初拥有的数组。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一行一个整数，表示 Simons 至少需要多少次操作。

在第一个测试用例中，数组一开始就是 cool 的，因此 Simons 不需要任何操作。答案为 $0$。 在第二个测试用例中，Simons 可以这样操作： - 选择下标 $3$，因为 $a_3 = \max(\{a_2, a_3, a_4\})$。然后，他删除 $a_2$。数组变为 $[4,3,2,5]$。 可以发现，数组现在已经 cool。于是答案为 $1$。 在第三个测试用例中，Simons 可以这样操作： - 选择下标 $2$，然后删除 $a_1$，数组变为 $[5,3,6,2,1]$。 - 选择下标 $3$，然后删除 $a_2$，数组变为 $[5,6,2,1]$。 - 选择下标 $2$，然后删除 $a_1$，数组变为 $[6,2,1]$。 因此，Simons 一共进行了 $3$ 次操作使数组变为 cool。 由 ChatGPT 5 翻译