题目描述

给你一个 $n$ 个整数的 $a[0…n−1]$ 数组。如果正好存在一个子数组 $a[l…r]$，满足以下规律，则该数组称为谷：

• $0≤l≤r≤n−1$，
• $a_l=a_{l+1}=a_{l+2}=……=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≤t≤10^4)$ 代表测试用例数。

每个测试用例的第一行包含一个整数 $n(1≤n≤2⋅10^5)$ ，代表数组的长度。

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

保证所有测试用例的 $n$ 之和不超过 $2⋅10^5$。

输出格式

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

答案不计大小写（例如，字符串 yEs、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

样例说明

题目描述中解释了前三个测试用例。