← 返回题目列表

AtCoder · arc102_d

F. BBuBBBlesort的复仇!

中文机器翻译题面 查看原题

分数: 1200 点

问题陈述

给你一个排列 1,2,...,N: p_1,p_2,...,p_N。确定状态是否在 通过执行任意多次以下操作可以到达 p_i=i 对于每个 i :

  • 选择三个元素 p_{i-1},p_{i},p_{i+1} (2\leq i\leq N-1) 这样 p_{i-1}>p_{i}>p_{i+1} 并颠倒这三个的顺序。

约束

  • 3 \leq N \leq 3 × 10^5
  • p_1,p_2,...,p_N 是一个排列 1,2,...,N.

输入

输入由标准输入按以下格式给出:

N
p_1
:
p_N

输出

如果状态 通过执行操作可以到达 p_i=i 对于每个 i ,打印 Yes;否则,打印 No.


示例输入 1

5
5
2
1
4
3

示例输出 1

Yes

状态 p_i=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.

示例输入 2

4
3
2
4
1

示例输出 2

No

示例输入 3

7
3
2
1
6
5
4
7

示例输出 3

Yes

示例输入 4

6
5
3
4
1
2
6

示例输出 4

No