Challenging Valleys solution codeforces

Challenging Valleys solution codeforces

You are given an array a[0n1]a[0…n−1] of nn integers. This array is called a “valley” if there exists exactly one subarray a[lr]a[l…r] such that:

  • 0lrn10≤l≤r≤n−1,
  • al=al+1=al+2==aral=al+1=al+2=⋯=ar,
  • l=0l=0 or al1>alal−1>al,
  • r=n1r=n−1 or ar<ar+1ar<ar+1.

Here are three examples:

The first image shows the array [3,2,2,1,2,2,33,2,2,1,2,2,3], it is a valley because only subarray with indices l=r=3l=r=3 satisfies the condition.

The second image shows the array [1,1,1,2,3,3,4,5,6,6,61,1,1,2,3,3,4,5,6,6,6], it is a valley because only subarray with indices l=0,r=2l=0,r=2 satisfies the codition.

The third image shows the array [1,2,3,4,3,2,11,2,3,4,3,2,1], it is not a valley because two subarrays l=r=0l=r=0 and l=r=6l=r=6 that satisfy the condition.

You are asked whether the given array is a valley or not.

Note that we consider the array to be indexed from 00.

Challenging Valleys solution codeforces

The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases.

The first line of each test case contains a single integer nn (1n21051≤n≤2⋅105) — the length of the array.

The second line of each test case contains nn integers aiai (1ai1091≤ai≤109) — the elements of the array.

It is guaranteed that the sum of nn over all test cases is smaller than 21052⋅105.

Challenging Valleys solution codeforces

For each test case, output “YES” (without quotes) if the array is a valley, and “NO” (without quotes) otherwise.

You can output the answer in any case (for example, the strings “yEs“, “yes“, “Yes” and “YES” will be recognized as a positive answer).

Example
input

Copy
6
7
3 2 2 1 2 2 3
11
1 1 1 2 3 3 4 5 6 6 6
7
1 2 3 4 3 2 1
7
9 7 4 6 9 9 10
1
1000000000
8
9 4 4 5 9 4 9 10
output

Copy
YES
YES
NO
YES
YES
NO
Note

The first three test cases are explained in the statement

Post navigation

Leave a Reply

Your email address will not be published.