题目描述

给定一个长度为 $n$ 的整数数组 $a[0 \dots n-1]$。如果存在且仅存在一个子数组 $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 \cdot 10^5$），表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$），表示数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果该数组是山谷，输出 "YES"（不含引号）；否则输出 "NO"（不含引号）。

你可以以任意大小写输出答案（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为正确答案）。

样例

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

YES
YES
NO
YES
YES
NO

样例说明

前三个测试用例的解释见题面。

由 ChatGPT 4.1 翻译

来源

Codeforces 1760D，英文题名 Challenging Valleys。