Two VIPs - Repovive Standard Round 6 | Repovive

18A. Two VIPs

500 pts1s256 MB

You are given a permutation $p$ of length $n$ .

You may perform the following operation any number of times:

Choose two adjacent elements of the permutation. You may swap them if at least one of them is equal to $1$ or $n$ .

Determine whether it is possible to sort the permutation in increasing order.

Constraints

$1 \le t \le 100$
$1 \le n \le 10^5$
The sum of $n$ over all test cases does not exceed $10^5$
$p$ is a permutation of $1,2,\ldots,n$

Input

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Output

For each test case, output Yes if the permutation can be sorted, and No otherwise.

The output is case-insensitive. For example, YES, Yes, and yes are all accepted.

\left. \begin{array}{l} \texttt{Yes or No} \end{array} \right\} \times t

Samples

Input

Case 1

2
2 1

Case 2

5
2 5 3 1 4

Case 3

5
3 1 2 5 4

Explanation

Case 1

Swap the two elements. This swap is allowed because the elements are $1$ and $n=2$ , and the permutation becomes $1,2$ .

Case 2

Move $1$ to the first position and then move $5$ to the last position:

$2,5,3,1,4 \rightarrow 2,5,1,3,4 \rightarrow 2,1,5,3,4 \rightarrow 1,2,5,3,4 \rightarrow 1,2,3,5,4 \rightarrow 1,2,3,4,5$ .

Every displayed swap contains either $1$ or $5$ .

Case 3

The value $3$ appears before $2$ . Neither of them is $1$ or $5$ , so they can never pass each other. Therefore, the permutation cannot be sorted.

Output

Case 1

Yes

Case 2

Yes

Case 3

No

Input

Case 1

8
2 3 8 4 5 1 6 7

Case 2

9
1 2 3 4 6 9 5 7 8

Explanation

Case 1

Move $1$ left until it reaches the first position, then move $8$ right until it reaches the last position.

Case 2

The value $6$ appears before $5$ , and neither value is a VIP. Their relative order cannot be changed.

Output

Case 1

Yes

Case 2

No

You are given a permutation $p$ of length $n$ .

You may perform the following operation any number of times:

Choose two adjacent elements of the permutation. You may swap them if at least one of them is equal to $1$ or $n$ .

Determine whether it is possible to sort the permutation in increasing order.

$1 \le t \le 100$
$1 \le n \le 10^5$
The sum of $n$ over all test cases does not exceed $10^5$
$p$ is a permutation of $1,2,\ldots,n$

t

\left. \begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

For each test case, output Yes if the permutation can be sorted, and No otherwise.

The output is case-insensitive. For example, YES, Yes, and yes are all accepted.

\left. \begin{array}{l} \texttt{Yes or No} \end{array} \right\} \times t

Swap the two elements. This swap is allowed because the elements are $1$ and $n=2$ , and the permutation becomes $1,2$ .

Move $1$ to the first position and then move $5$ to the last position:

$2,5,3,1,4 \rightarrow 2,5,1,3,4 \rightarrow 2,1,5,3,4 \rightarrow 1,2,5,3,4 \rightarrow 1,2,3,5,4 \rightarrow 1,2,3,4,5$ .

Every displayed swap contains either $1$ or $5$ .

The value $3$ appears before $2$ . Neither of them is $1$ or $5$ , so they can never pass each other. Therefore, the permutation cannot be sorted.

Move $1$ left until it reaches the first position, then move $8$ right until it reaches the last position.

The value $6$ appears before $5$ , and neither value is a VIP. Their relative order cannot be changed.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

18A. Two VIPs

Constraints

Input

Output

Samples

18A. Two VIPs

Constraints

Input

Output

Samples