実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1200 点
問題文
1,2,...,N の並び替え p_1,p_2,...,p_N が与えられます。以下の操作を好きなだけ繰り返してすべての i に対して p_i=i となるようにできるか判定してください。
- p_{i-1}>p_{i}>p_{i+1} なる 3 項組 (2\leq i\leq N-1) を選び、この 3 項を逆順に並び替える。
制約
- 3 \leq N \leq 3 × 10^5
- p_1,p_2,...,p_N は 1,2,...,N の並び替えである
入力
入力は以下の形式で標準入力から与えられる。
N p_1 : p_N
出力
操作を繰り返してすべての i に対して p_i=i となるようにできる場合は Yes
を、そうでない場合は No
を出力せよ。
入力例 1
5 5 2 1 4 3
出力例 1
Yes
以下の操作ですべての 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 となる。
入力例 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
Score : 1200 points
Problem Statement
You are given a permutation of 1,2,...,N: p_1,p_2,...,p_N. Determine if the state where p_i=i for every i can be reached by performing the following operation any number of times:
- Choose three elements p_{i-1},p_{i},p_{i+1} (2\leq i\leq N-1) such that p_{i-1}>p_{i}>p_{i+1} and reverse the order of these three.
Constraints
- 3 \leq N \leq 3 × 10^5
- p_1,p_2,...,p_N is a permutation of 1,2,...,N.
Input
Input is given from Standard Input in the following format:
N p_1 : p_N
Output
If the state where p_i=i for every i can be reached by performing the operation, print Yes
; otherwise, print No
.
Sample Input 1
5 5 2 1 4 3
Sample Output 1
Yes
The state where p_i=i for every i can be reached as follows:
- Reverse the order of p_1,p_2,p_3. The sequence p becomes 1,2,5,4,3.
- Reverse the order of p_3,p_4,p_5. The sequence p becomes 1,2,3,4,5.
Sample Input 2
4 3 2 4 1
Sample Output 2
No
Sample Input 3
7 3 2 1 6 5 4 7
Sample Output 3
Yes
Sample Input 4
6 5 3 4 1 2 6
Sample Output 4
No