题目描述

给定 $1,2,\ldots,N$ 的一个排列 $p_1,p_2,\ldots,p_N$。你可以任意多次重复以下操作，判断是否可以使得对于所有 $i$，都有 $p_i=i$。

• 选择满足 $p_{i-1} > p_i > p_{i+1}$ 的三元组（$2 \leq i \leq N-1$），将这三个元素逆序排列。

输入格式

输入以以下格式从标准输入读入。

$N$ $p_1$ $p_2$ $\ldots$ $p_N$

输出格式

如果可以通过若干次操作使得对于所有 $i$，都有 $p_i=i$，则输出 Yes，否则输出 No。

样例 1

输入

5
5
2
1
4
3

输出

Yes

样例 2

输入

4
3
2
4
1

输出

No

样例 3

输入

7
3
2
1
6
5
4
7

输出

Yes

样例 4

输入

6
5
3
4
1
2
6

输出

No

说明/提示

限制条件

• $3 \leq N \leq 3 \times 10^5$
• $p_1,p_2,\ldots,p_N$ 是 $1,2,\ldots,N$ 的一个排列

样例解释 1

可以通过以下操作使得对于所有 $i$，都有 $p_i=i$。

• 将 $p_1,p_2,p_3$ 逆序排列。此时序列 $p$ 变为 $1,2,5,4,3$。
• 将 $p_3,p_4,p_5$ 逆序排列。此时序列 $p$ 变为 $1,2,3,4,5$。

由 ChatGPT 4.1 翻译