D - Permutation Ordering

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)


配点:200200

問題文

(1,2,,N)(1, 2, \ldots, N) の順列 P=(P1,P2,,PN)P = (P_1, P_2, \ldots, P_N) があります.

次の操作を 00 回以上何度でも行えます:

  • 1i<jN1 \leq i < j \leq N なる 22 整数 i,ji, j を自由に選び,PiP_iPjP_j との値を交換する.

P=(1,2,,N)P = (1, 2, \ldots, N) とするために必要な操作回数の最小値を求めてください.

制約

  • 1Φ1051 \leq \Phi \leq 10^5
  • 1N1 \leq N
  • ϕΦϕ(N)105\sum_{\phi} \Phi_{\phi}(N) \leq 10^5
  • 1PiN(1iN)1 \leq P_i \leq N \scriptsize \; (1 \leq i \leq N)
  • PiPj(1i<jN)P_i \not= P_j \scriptsize \; (1 \leq i < j \leq N)
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NN
P1P2PNP_1 \enspace P_2 \enspace \ldots \enspace P_N

出力

答えを出力せよ.

サンプル

入力例1
1
5
5 1 3 4 2
出力例1
2

たとえば次のように達成可能です:

  • 1 ⁣:(i,j)=(1,5)1 \colon (i, j) = (1, 5) として操作を行う.
    • P=(2,1,3,4,5)P = (2, 1, 3, 4, 5) となる.
  • 2 ⁣:(i,j)=(1,2)2 \colon (i, j) = (1, 2) として操作を行う.
    • P=(1,2,3,4,5)P = (1, 2, 3, 4, 5) となる.

入力例2
3
4
1 2 3 4
4
4 3 2 1
6
1 3 4 6 2 5
出力例2
0
2
4

提出


Go (1.21)