A16863 | 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 至少需要多少次操作。