CF1467B Hills And Valleys

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。我们称下标 $j$（$2 \le j \le n-1$）为“山峰”，如果 $a_j > a_{j+1}$ 且 $a_j > a_{j-1}$；称其为“山谷”，如果 $a_j < a_{j+1}$ 且 $a_j < a_{j-1}$。 我们定义一个序列的“威慑值”为该序列中山峰和山谷的总数。你可以将序列中的恰好一个整数修改为任意你想要的数，或者保持序列不变。请问你能得到的最小威慑值是多少？

输入的第一行包含一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。 每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示你能得到的最小威慑值。

在第一个测试用例中，将 $a_2$ 改为 $2$ 后，没有山峰也没有山谷。 在第二个测试用例中，最优解是保持数组不变。 在第三个测试用例中，将 $a_3$ 改为 $6$ 后，只剩下一个山谷（在下标 $5$ 处）。 在第四个测试用例中，将 $a_3$ 改为 $6$ 后，没有山峰也没有山谷。 由 ChatGPT 4.1 翻译