1713B.md (1965B)
1 Source: https://codeforces.com/problemset/problem/1713/B 2 3 B. Optimal Reduction 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Consider an array $a$ of $n$ positive integers. 22 23 You may perform the following operation: 24 25 * select two indices $l$ and $r$ ($1 \leq l \leq r \leq n$), then 26 * decrease all elements $a_l, a_{l + 1}, \dots, a_r$ by $1$. 27 28 Let's call $f(a)$ the minimum number of operations needed to change array $a$ into an array of $n$ zeros. 29 30 Determine if for all permutations$^\dagger$ $b$ of $a$, $f(a) \leq f(b)$ is true. 31 32 $^\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]$. 33 34 Input 35 36 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 37 38 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$. 39 40 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$. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 43 44 Output 45 46 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. 47 48 You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response). 49 50 Example 51 52 Input 53 54 ``` 55 3 56 57 4 58 59 2 3 5 4 60 61 3 62 63 1 2 3 64 65 4 66 67 3 1 3 2 68 ``` 69 70 Output 71 72 ``` 73 YES 74 YES 75 NO 76 ``` 77 78 Note 79 80 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$. 81 82 In the third test case, we need $5$ operations to change all elements to $0$, while $[2, 3, 3, 1]$ only needs $3$ operations.