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

18A. Two VIPs

Constraints

Input

Output

Samples

18A. Two VIPs

Constraints

Input

Output

Samples