题目描述

有 $n+2$ 个位置，编号从 $0$ 到 $n+1$。初始时，对于每个 $1 \le i \le n$，位置 $i$ 上有一个值为 $w_i$ 的元素，而位置 $0$ 和 $n+1$ 均为空。

你需要选择一个整数 $k$。随后，所有元素同时且恰好移动一次，移动规则如下：

• 如果 $w_i < k$，位于位置 $i$ 的元素移动到位置 $i-1$；
• 如果 $w_i > k$，位于位置 $i$ 的元素移动到位置 $i+1$；
• 如果 $w_i = k$，整个移动过程立即失败。

如果移动没有失败，且在移动完成后，从 $1$ 到 $n$ 的每个位置都恰好包含一个元素，则称整数 $k$ 是完美的。

请判断是否存在这样一个完美的整数 $k$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 100$）。
• 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^9$）—— 表示初始时各个元素对应的权重。

输出格式

对于每个测试用例，如果存在完美的整数 $k$，输出 YES；否则输出 NO。

样例输入 1

6
1
7
2
3 1
2
2 1
4
9 1 7 2
4
9 8 7 1
6
1000000000 1 9 2 8 3

样例输出 1

NO
YES
NO
YES
NO
YES

说明

样例解释

• 在第 $1$ 个测试用例中，唯一的一个元素要么离开位置 $1$，要么由于权重等于 $k$ 导致移动失败。因此不存在合适的整数 $k$。
• 在第 $2$ 个测试用例中，可以选择 $k=2$。权重为 $3$ 的元素向右移动，权重为 $1$ 的元素向左移动，从而在位置 $1$ 和位置 $2$ 上各留下一个元素。
• 在第 $3$ 个测试用例中，若要让两个位置最终都被占据，则需要 $1 < k < 2$，但这对于整数 $k$ 来说是不可能的。
• 在第 $4$ 个测试用例中，选择 $k=5$ 是合适的：位置 $1$ 和 $3$ 的元素向右移动，而位置 $2$ 和 $4$ 的元素向左移动。完成后，从 $1$ 到 $4$ 的每个位置恰好包含一个元素。
• 在第 $5$ 个测试用例中，位置 $2$ 的元素必须向左移动，这要求 $k > 8$；而位置 $3$ 的元素必须向右移动，这要求 $k < 7$。这两个要求是矛盾的。
• 在第 $6$ 个测试用例中，可以选择 $k=4$。所有位于奇数位置的元素向右移动，所有位于偶数位置的元素向左移动，最终位置 $1$ 到 $6$ 的每个位置都恰好包含一个元素。

数据范围

• 对于所有测试点，保证 $1 \le t \le 500$。
• 对于每个测试用例，保证 $1 \le n \le 100$。
• 对于每个测试用例，保证 $1 \le w_i \le 10^9$。
• 保证所有的输入数值均为整数。