Behind the Peak - Repovive Standard Round 6 | Repovive

18F. Behind the Peak

3000 pts2s256 MB

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

In one operation, you may choose an index $i$ such that $1 \le i \le n-2$ and

p_{i+1}>\max(p_i,p_{i+2}),

then swap $p_i$ and $p_{i+2}$ .

Determine whether it is possible, after performing any number of operations, to make $p_i<p_{i+2}$ hold for every $1 \le i \le n-2$ .

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 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 required permutation can be obtained, and No otherwise.

The answer 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

3
2 3 1

Case 2

5
3 4 2 5 1

Case 3

4
3 1 2 4

Explanation

Case 1

Choose $i=1$ . Since $p_2=3>\max(2,1)$ , swap the elements at indices $1$ and $3$ . The sequence becomes $1,3,2$ , which satisfies the required condition.

Case 2

Choose $i=1$ and swap indices $1$ and $3$ . The sequence becomes $2,4,3,5,1$ .

Next, choose $i=3$ and swap indices $3$ and $5$ . The sequence becomes $2,4,1,5,3$ .

Finally, choose $i=1$ and swap indices $1$ and $3$ . The sequence becomes $1,4,2,5,3$ , which satisfies the required condition.

Case 3

It is impossible to reach a permutation satisfying the required condition.

Output

Case 1

Yes

Case 2

Yes

Case 3

No

Input

Case 1

8
1 3 4 6 7 5 8 2

Case 2

10
10 9 8 7 6 5 4 3 2 1

Explanation

Case 1

Swap the elements at indices $(4,6)$ , then $(6,8)$ , then $(4,6)$ , and finally $(2,4)$ . These operations produce a permutation satisfying the required condition.

Case 2

It is impossible to reach a permutation satisfying the required condition.

Output

Case 1

Yes

Case 2

No

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

In one operation, you may choose an index $i$ such that $1 \le i \le n-2$ and

p_{i+1}>\max(p_i,p_{i+2}),

then swap $p_i$ and $p_{i+2}$ .

Determine whether it is possible, after performing any number of operations, to make $p_i<p_{i+2}$ hold for every $1 \le i \le n-2$ .

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 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 required permutation can be obtained, and No otherwise.

The answer 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

Choose $i=1$ . Since $p_2=3>\max(2,1)$ , swap the elements at indices $1$ and $3$ . The sequence becomes $1,3,2$ , which satisfies the required condition.

Choose $i=1$ and swap indices $1$ and $3$ . The sequence becomes $2,4,3,5,1$ .

Next, choose $i=3$ and swap indices $3$ and $5$ . The sequence becomes $2,4,1,5,3$ .

Finally, choose $i=1$ and swap indices $1$ and $3$ . The sequence becomes $1,4,2,5,3$ , which satisfies the required condition.

Swap the elements at indices $(4,6)$ , then $(6,8)$ , then $(4,6)$ , and finally $(2,4)$ . These operations produce a permutation satisfying the required condition.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

18F. Behind the Peak

Constraints

Input

Output

Samples

18F. Behind the Peak

Constraints

Input

Output

Samples