Optimal Reduction (Codeforces 1713B)
Tags: Others, sortings

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

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

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

Note: 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.

Sample Inputs:
3
4
2 3 5 4
3
1 2 3
4
3 1 3 2

Sample Outputs:
YES
YES
NO

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            arr = list(map(int, input().split()))
            flag = True
            valley = False
            if n > 2:
                for j in range(1, n - 1):
                    if arr[j - 1] > arr[j]:
                        valley = True
                    if valley and arr[j] < arr[j + 1]:
                        flag = False
                        break
            if flag:
                result.append('YES')
            else:
                result.append('NO')
        for x in result:
            print(x)
if __name__ == '__main__':
    sol = Solution()
    sol.solve()

Solution (Python):
import sys
input = sys.stdin.readline
import math
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    suff = 0
    pre = 0
    i = 0
    while i < n - 1:
        if a[i + 1] >= a[i]:
            suff += 1
        else:
            break
        i += 1
    while i < n - 1:
        if a[i + 1] <= a[i]:
            pre += 1
        i += 1
    if suff + pre + 1 >= n:
        print('YES')
    else:
        print('NO')

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    I = list(map(int, input().split()))
    i = 0
    check = True
    while i < n - 1 and I[i] <= I[i + 1]:
        i += 1
    while i < n - 1:
        if I[i] < I[i + 1]:
            check = False
            break
        i += 1
    if check:
        print('YES')
    else:
        print('NO')