[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$a$ of n$n$ positive integers.

You may perform the following operation:

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

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

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

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 occupied

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

Input

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

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

The second line contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$) — description of the array a$a$.

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

Output

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