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

My submissions

Announcements

18F. Behind the Peak

Constraints

Input

Output

Samples

18F. Behind the Peak

Constraints

Input

Output

Samples