分数: 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