[Solution] Optimal Reduction solution codeforces

Optimal Reduction solution codeforces – Consider an array 𝑎a of 𝑛n positive integers.

You may perform the following operation:

  • select two indices 𝑙l and 𝑟r (1𝑙𝑟𝑛1≤l≤r≤n), then
  • decrease all elements 𝑎𝑙,𝑎𝑙+1,,𝑎𝑟al,al+1,…,ar by 11.

Table of Contents

[Solution] Optimal Reduction solution codeforces

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 𝑏b of 𝑎a𝑓(𝑎)𝑓(𝑏)f(a)≤f(b) is true.

 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][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 (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛1051≤n≤105) — the length of the array 𝑎a.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — description of the array 𝑎a.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

[Solution] Optimal Reduction solution codeforces

For each test case, print “YES” (without quotes) if for all permutations 𝑏b of 𝑎a𝑓(𝑎)𝑓(𝑏)f(a)≤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).

Example
input

Copy
3
4
2 3 5 4
3
1 2 3
4
3 1 3 2

[Solution] Optimal Reduction solution codeforces

output

Copy
YES
YES
NO
Note

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

In the third test case, we need 55 operations to change all elements to 00, while [2,3,3,1][2,3,3,1] only needs 33 operations.

 

For Solution

Click Here

Leave a Comment