CF1467B.Hills And Valleys

You are given a sequence of $n$ integers $a_1$, $a_2$, ..., $a_n$. Let us call an index $j$ ($2 \le j \le {{n-1}}$) a hill if $a_j \gt a_{{j+1}}$ and $a_j \gt a_{{j-1}}$; and let us call it a valley if $a_j \lt a_{{j+1}}$ and $a_j \lt a_{{j-1}}$.

Let us define the intimidation value of a sequence as the sum of the number of hills and the number of valleys in the sequence. You can change exactly one integer in the sequence to any number that you want, or let the sequence remain unchanged. What is the minimum intimidation value that you can achieve?

给你一个长度为 $n$ 的整数序列 $a_1$, $a_2$, ..., $a_n$。我们称下标 $j$（其中 $2 \le j \le n-1$）为山峰，当且仅当 $a_j \gt a_{{j+1}}$ 且 $a_j \gt a_{{j-1}}$；称其为山谷，当且仅当 $a_j \lt a_{{j+1}}$ 且 $a_j \lt a_{{j-1}}$。

我们定义该序列的威慑值（intimidation value）为序列中山峰个数与山谷个数之和。你可以恰好修改序列中的一个整数为任意你想要的整数（也可以选择不作任何修改）。请问：你能达到的最小威慑值是多少？

The first line of the input contains a single integer $t$ ($1 \le t \le 10000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3\cdot10^5$).

The second line of each test case contains $n$ space-separated integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$).

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

输入的第一行包含一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3\cdot10^5$）。

每个测试用例的第二行包含 $n$ 个以空格分隔的整数 $a_1$, $a_2$, ..., $a_n$（$1 \le a_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $3\cdot10^5$。

For each test case, print a single integer — the minimum intimidation value that you can achieve.

对于每个测试用例，输出一个整数——你能达到的最小恐吓值。

In the first test case, changing $a_2$ to $2$ results in no hills and no valleys.

In the second test case, the best answer is just to leave the array as it is.

In the third test case, changing $a_3$ to $6$ results in only one valley (at the index $5$).

In the fourth test case, changing $a_3$ to $6$ results in no hills and no valleys.

在第一个测试用例中，将 $a_2$ 改为 $2$ 后，数组中既没有山峰也没有山谷。

在第二个测试用例中，最优方案就是保持数组不变。

在第三个测试用例中，将 $a_3$ 改为 $6$ 后，数组中仅存在一个山谷（位于索引 $5$ 处）。

在第四个测试用例中，将 $a_3$ 改为 $6$ 后，数组中既没有山峰也没有山谷。