考虑一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。
您可以执行以下操作:
- 选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$),然后
- 将所有元素 $$$a_l, a_{l + 1}, \dots, a_r$$$ 减少 $$$1$$$。
我们将 $$$f(a)$$$ 称为将数组 $$$a$$$ 更改为 $$$n$$$ 零数组所需的最少操作数。
确定对于 $$$a$$$ 的所有排列$$$^\dagger$$$ $$$b$$$,$$$f(a) \leq f(b)$$$ 是否为真。
$$$^\dagger$$$ 数组 $$$b$$$ 是数组 $$$a$$$ 的排列,如果 $$$b$$$ 由 $$$a$$$ 的元素以任意顺序组成。例如,$$$[4,2,3,4]$$$ 是 $$$[3,2,4,4]$$$ 的排列,而 $$$[1,2,2]$$$ 不是 $$$[1,2,3]$$$ 的排列。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的描述。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,如果对于 $$$a$$$ 的所有排列 $$$b$$$,$$$f(a) \leq f(b)$$$ 为真,则打印“YES”(不带引号),否则打印“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
3 4 2 3 5 4 3 1 2 3 4 3 1 3 2
输出 #1
YES YES NO
注意
在第一个测试用例中,我们可以在$$$5$$$操作中将所有元素更改为$$$0$$$。可以证明$$$[2,3,5,4]$$$的排列不需要少于$$$5$$$操作来将所有元素更改为$$$0$$$。
在第三个测试用例中,我们需要 $$$5$$$ 操作将所有元素更改为 $$$0$$$,而 $$$[2, 3, 3, 1]$$$ 只需要 $$$3$$$ 操作。