CF2205D.Simons and Beating Peaks

My loveliest wishes dissolved into the air; At eighteen, I poured my dreams into the mic to share.

— SHUN, 720

We call an array $b$ of length $m$ cool if and only if:

• There exists no index $i$ ($1 \lt i \lt m$) such that $b_i=\max({b_{i-1}, b_i, b_{i+1}})$.

Simons has an array $a$ of size $n$. Initially, the array is a permutation$^{\text{∗}}$.

He must perform the following operation until the array is cool:

• Choose an index $i$ ($1 \lt i \lt n$) such that $a_i=\max({a_{i-1}, a_i, a_{i+1}})$.
• Then, he can remove either $a_{i-1}$ or $a_{i+1}$ from the array. After removal, a gap appears in the array, and the left and right sides of the gap will be rejoined.

Find the minimum number of operations for Simons to perform.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

我最美好的愿望消散在空气中；十八岁那年，我将梦想倾注于麦克风中与人分享。

— SHUN，720

我们称一个长度为 $m$ 的数组 $b$ 是“酷”的，当且仅当：

• 不存在下标 $i$（满足 $1 \lt i \lt m$），使得 $b_i=\max({b_{i-1}, b_i, b_{i+1}})$。

西蒙斯有一个长度为 $n$ 的数组 $a$。初始时，该数组是一个排列$^{\text{∗}}$。

他必须重复执行以下操作，直到数组变为“酷”的为止：

• 选择一个下标 $i$（满足 $1 \lt i \lt n$），使得 $a_i=\max({a_{i-1}, a_i, a_{i+1}})$；
• 然后，他可以从数组中删除 $a_{i-1}$ 或 $a_{i+1}$ 中的任意一个元素。删除后，数组中会出现一个空缺，空缺左右两侧的元素将重新连接。

求西蒙斯需要执行的最少操作次数。

$^{\text{∗}}$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中却出现了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5\cdot 10^4$). The description of the test cases follows.

The first line contains an integer $n$ ($3\le n\le 5\cdot 10^5$) — the size of $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le n$, all $a_i$-s are distinct) — the array Simons has initially.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 互不相同）—— Simons 初始拥有的数组。

保证所有测试用例中 $n$ 的总和不超过 $5\cdot 10^5$。

For each test case, print a single integer — the minimum number of operations for Simons to perform.

对于每个测试用例，输出一个整数——西蒙需要执行的最少操作次数。

In the first test case, the array is cool initially, so Simons can't perform any operation. The answer is $0$.

In the second test case, Simons can perform as follows:

• Choose index $3$, because $a_3=\max({a_2,a_3,a_4})$. Then, he removes $a_{2}$ from the array. The array becomes $[4,3,2,5]$.

We can see the array is cool now. Thus, the answer is $1$.

In the third test case, Simons can perform as follows:

• Choose index $2$. Then, he removes $a_1$ from the array. The array becomes $[5,3,6,2,1]$.
• Choose index $3$. Then, he removes $a_2$ from the array. The array becomes $[5,6,2,1]$.
• Choose index $2$. Then, he removes $a_1$ from the array. The array becomes $[6,2,1]$.

Thus, Simons makes the array cool in $3$ operations.

在第一个测试用例中，数组初始时就是“酷”的，因此 Simon 无法执行任何操作。答案为 $0$。

在第二个测试用例中，Simon 可以按如下方式操作：

• 选择下标 $3$，因为 $a_3=\max({a_2,a_3,a_4})$。然后他将 $a_{2}$ 从数组中删除。数组变为 $[4,3,2,5]$。

此时可见数组已变为“酷”的。因此答案为 $1$。

在第三个测试用例中，Simon 可以按如下方式操作：

• 选择下标 $2$。然后他将 $a_1$ 从数组中删除。数组变为 $[5,3,6,2,1]$。
• 选择下标 $3$。然后他将 $a_2$ 从数组中删除。数组变为 $[5,6,2,1]$。
• 选择下标 $2$。然后他将 $a_1$ 从数组中删除。数组变为 $[6,2,1]$。

因此，Simon 经过 $3$ 次操作使数组变为“酷”的。