A15362. 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]$ .

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$ .

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).

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.