给你一个 $$$n$$$ 整数序列 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$。如果 $$$a_j > a_{{j+1}}$$$ 且 $$$a_j > a_{{j-1}}$$$,我们称索引 $$$j$$$ ($$$2 \le j \le {{n-1}}$$$) 为山;如果 $$$a_j < a_{{j+1}}$$$ 且 $$$a_j < a_{{j-1}}$$$,我们称其为山谷。
让我们将序列的恐吓值定义为序列中山丘数量和山谷数量的总和。您可以将序列中的一个整数更改为您想要的任何数字,或者让序列保持不变。你能达到的最小恐吓值是多少?
输入
输入的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - 您可以实现的最小恐吓值。
示例
输入 #1
4 3 1 5 3 5 2 2 2 2 2 6 1 6 2 5 2 10 5 1 6 2 5 1
输出 #1
0 0 1 0
注意
在第一个测试用例中,将 $$$a_2$$$ 更改为 $$$2$$$ 会导致没有山丘和山谷。
在第二个测试用例中,最好的答案是让数组保持原样。
在第三个测试用例中,将 $$$a_3$$$ 更改为 $$$6$$$ 只会产生一个谷值(位于索引 $$$5$$$ 处)。
在第四个测试用例中,将 $$$a_3$$$ 更改为 $$$6$$$ 会导致没有山丘和山谷。