给你一个 $$$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
注意
声明中解释了前三个测试用例。