← 返回题目列表

Codeforces · 1760/D

D. 具有挑战性的山谷

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

给你一个 $$$a[0 \dots n-1]$$$ 的数组 $$$n$$$ 个整数。如果恰好存在一个子数组 $$$a[l \dots r]$$$ ,则该数组称为“谷”,使得:

- $$$0 \le l \le r \le n-1$$$,
- $$$a_l = a_{l+1} = a_{l+2} = \dots = a_r$$$,
- $$$l = 0$$$ 或 $$$a_{l-1} > a_{l}$$$,
- $$$r = n-1$$$ 或 $$$a_r < a_{r+1}$$$。

以下是三个示例:

第一个图像显示数组 [$$$3, 2, 2, 1, 2, 2, 3$$$],它是一个山谷,因为只有索引为 $$$l=r=3$$$ 的子数组满足条件。

第二张图显示了数组 [$$$1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6$$$],它是一个山谷,因为只有索引为 $$$l=0, r=2$$$ 的子数组满足条件。

第三张图显示了数组 [$$$1, 2, 3, 4, 3, 2, 1$$$],它不是一个山谷,因为有两个子数组 $$$l=r=0$$$ 和 $$$l=r=6$$$ 满足条件。

系统会询问您给定的数组是否为山谷。

请注意,我们认为数组是从 $$$0$$$ 开始索引的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和小于 $$$2\cdot10^5$$$。

输出

对于每个测试用例,如果数组是山谷,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10

输出 #1

YES
YES
NO
YES
YES
NO

注意

声明中解释了前三个测试用例。