1760D.md (2109B)
1 Source: https://codeforces.com/problemset/problem/1760/D 2 3 D. Challenging Valleys 4 5 time limit per test 6 7 2 seconds 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 You are given an array $a[0 \dots n-1]$ of $n$ integers. This array is called a "valley" if there exists exactly one subarray $a[l \dots r]$ such that: 22 23 * $0 \le l \le r \le n-1$, 24 * $a_l = a_{l+1} = a_{l+2} = \dots = a_r$, 25 * $l = 0$ or $a_{l-1} \gt a_{l}$, 26 * $r = n-1$ or $a_r \lt a_{r+1}$. 27 28 Here are three examples: 29 30  31 32 The first image shows the array [$3, 2, 2, 1, 2, 2, 3$], it is a valley because only subarray with indices $l=r=3$ satisfies the condition. 33 34 The second image shows the array [$1, 1, 1, 2, 3, 3, 4, 5, 6, 6, 6$], it is a valley because only subarray with indices $l=0, r=2$ satisfies the codition. 35 36 The third image shows the array [$1, 2, 3, 4, 3, 2, 1$], it is not a valley because two subarrays $l=r=0$ and $l=r=6$ that satisfy the condition. 37 38 You are asked whether the given array is a valley or not. 39 40 Note that we consider the array to be indexed from $0$. 41 42 Input 43 44 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 45 46 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the array. 47 48 The second line of each test case contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^9$) — the elements of the array. 49 50 It is guaranteed that the sum of $n$ over all test cases is smaller than $2\cdot10^5$. 51 52 Output 53 54 For each test case, output "YES" (without quotes) if the array is a valley, and "NO" (without quotes) otherwise. 55 56 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer). 57 58 Example 59 60 Input 61 62 ``` 63 6 64 65 7 66 67 3 2 2 1 2 2 3 68 69 11 70 71 1 1 1 2 3 3 4 5 6 6 6 72 73 7 74 75 1 2 3 4 3 2 1 76 77 7 78 79 9 7 4 6 9 9 10 80 81 1 82 83 1000000000 84 85 8 86 87 9 4 4 5 9 4 9 10 88 ``` 89 90 Output 91 92 ``` 93 YES 94 YES 95 NO 96 YES 97 YES 98 NO 99 ``` 100 101 Note 102 103 The first three test cases are explained in the statement.