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](https://open.spotify.com/track/3bhQrFuaaPk8pMMb7TcU2d) 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).

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 $ .

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.