CF1713B.Optimal Reduction

Consider an array $a$ of $n$ positive integers.

You may perform the following operation:

• select two indices $l$ and $r$ ($1 \leq l \leq r \leq n$), then
• decrease all elements $a_l, a_{l + 1}, \dots, a_r$ by $1$.

Let's call $f(a)$ the minimum number of operations needed to change array $a$ into an array of $n$ zeros.

Determine if for all permutations$^\dagger$ $b$ of $a$, $f(a) \leq f(b)$ is true.

$^\dagger$ An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary order. For example, $[4,2,3,4]$ is a permutation of $[3,2,4,4]$ while $[1,2,2]$ is not a permutation of $[1,2,3]$.

考虑一个包含 $n$ 个正整数的数组 $a$。

你可以执行以下操作：

• 选择两个下标 $l$ 和 $r$（满足 $1 \leq l \leq r \leq n$），然后
• 将所有元素 $a_l, a_{l + 1}, \dots, a_r$ 同时减 $1$。

定义 $f(a)$ 为将数组 $a$ 变为全零数组所需的最少操作次数。

判断是否对 $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]$ 的排列。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — description of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, print "YES" (without quotes) if for all permutations $b$ of $a$, $f(a) \leq f(b)$ is true, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

对于每个测试用例，如果对数组 $a$ 的所有排列 $b$ 均满足 $f(a) \leq f(b)$，则输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

你可以以任意大小写形式输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes" 和 "Yes" 均会被识别为肯定回答）。

In the first test case, we can change all elements to $0$ in $5$ operations. It can be shown that no permutation of $[2, 3, 5, 4]$ requires less than $5$ operations to change all elements to $0$.

In the third test case, we need $5$ operations to change all elements to $0$, while $[2, 3, 3, 1]$ only needs $3$ operations.

在第一个测试用例中，我们可以在 $5$ 次操作内将所有元素变为 $0$。可以证明：对于排列 $[2, 3, 5, 4]$ 的任意排列，将其所有元素变为 $0$ 所需的操作次数均不少于 $5$。

在第三个测试用例中，我们需要 $5$ 次操作将所有元素变为 $0$，而 $[2, 3, 3, 1]$ 仅需 $3$ 次操作。