難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) Lv.4.0 (4票)

投票の分布
  1. Lv.10票
  2. Lv.20票
  3. Lv.31票
  4. Lv.42票
  5. Lv.51票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

adjacent swap

作成者 npnp

難易度(作成者設定) Lv.3

難易度(投票) Lv.4.0 (4票)

実行時間制限
2 秒
メモリ制限
512 MiB

この問題は沼津高専 高専祭でnpnpが出題した景品付き問題を一般化した問題です。

問題文

11 から NN までの整数をちょうど 11 回ずつ含む順列 P=(P1,P2,…,PN)P = (P_1, P_2, \ldots, P_N) が与えられます。

あなたは、以下の操作を繰り返し行うことができます。

  • 1≤i<N1 \le i < N を満たす整数 ii を選び、PiP_i と Pi+1P_{i+1} を入れ替える。

ちょうど奇数回の操作で PP を (1,2,…,N)(1, 2, \ldots, N) に並び替えることができるかどうかを判定してください。

制約

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • PP は 11 から NN までの整数をちょうど 11 回ずつ含む順列である
  • 入力はすべて整数である

入力形式

入力は以下の形式で与えられる。

N
P_1 P_2 \ldots P_N

出力形式

ちょうど奇数回の操作で PP を (1,2,…,N)(1, 2, \ldots, N) に並び替えることができるなら Yes を、できないなら No を出力してください。

入力例 1

3
2 1 3

出力例 1

Yes

入力例 2

3
1 2 3

出力例 2

No

入力例 3

4
2 3 4 1

出力例 3

Yes