## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Optimal Reduction Codeforces Solution

B. Optimal Reduction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

You may perform the following operation:

• select two indices $l$ and $r$ ($1\le l\le r\le n$), then
• decrease all elements ${a}_{l},{a}_{l+1},\dots ,{a}_{r}$ by $1$.

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

Determine if for all permutations${}^{†}$ $b$ of $a$$f\left(a\right)\le f\left(b\right)$ is true.

${}^{†}$ An array $b$ is a permutation of an array $a$ if $b$ consists of the elements of $a$ in arbitrary

Solution Click Below:-  👉

👇👇👇👇👇

occupied

order. For example, $\left[4,2,3,4\right]$ is a permutation of $\left[3,2,4,4\right]$ while $\left[1,2,2\right]$ is not a permutation of $\left[1,2,3\right]$.

Input

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

The first line of each test case contains a single integer $n$ ($1\le n\le {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}$.

Output

For each test case, print "YES" (without quotes) if for all permutations $b$ of $a$$f\left(a\right)\le f\left(b\right)$ 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).