← 返回题目列表

Codeforces · 1467/B

B. 丘陵和山谷

中文机器翻译题面 查看原题

给你一个 $$$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$$$ 会导致没有山丘和山谷。