AT_abc436_e [ABC436E] Minimum Swap

$ (1,2,\ldots,N) $ を並べ替えた整数列 $ P=(P _ 1,P _ 2,\ldots,P _ N) $ が与えられます。 ここで、 $ P $ は $ (1,2,\ldots,N) $ と等しくないことが保証されます。 あなたは、次の操作を $ 0 $ 回以上行って $ P $ を列 $ (1,2,\ldots,N) $ と一致させたいです。 - $ 1\le i\lt j\le N $ を満たす整数の組 $ (i,j) $ をひとつ選ぶ。 $ P _ i $ と $ P _ j $ の値を入れ替える。 $ P $ を列 $ (1,2,\ldots,N) $ と一致させるために必要な最小の操作回数を $ K $ 回とします。 $ K $ 回の操作で $ P $ を列 $ (1,2,\ldots,N) $ と一致させるような操作列の **$ \mathbf{1} $ 回目の操作として**あり得る操作の数を求めてください。 ただし、 $ 2 $ つの操作は選んだ整数の組 $ (i,j) $ が異なるとき、またそのときに限り区別します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P _ 1 $ $ P _ 2 $ $ \ldots $ $ P _ N $

答えを出力せよ。

### Sample Explanation 1 例えば、次のようにして $ 3 $ 回の操作で目標を達成することができます。 - $ (i,j)=(1,2) $ を選ぶ。 $ P=(1,3,4,2,5) $ となる。 - $ (i,j)=(2,4) $ を選ぶ。 $ P=(1,2,4,3,5) $ となる。 - $ (i,j)=(3,4) $ を選ぶ。 $ P=(1,2,3,4,5) $ となる。 $ 2 $ 回以下の操作で目標を達成することはできないので、 $ K=3 $ です。 上の説明の通り、最初の操作で $ (1,2) $ を選ぶと $ 3 $ 回の操作で目標を達成できます。 その他にも、最初の操作で $ (1,3),(1,4),(2,3),(2,4),(3,4) $ のいずれかを選んだ場合にはそのあとの $ 2 $ 回の操作を適切に行うことで $ P=(1,2,3,4,5) $ とすることができます。 よって、`6` を出力してください。 ### Constraints - $ 2\le N\le3\times10 ^ 5 $ - $ 1\le P _ i\le N\ (1\le i\le N) $ - $ P _ i\ne P _ j\ (1\le i\lt j\le N) $ - $ i\ne P _ i $ を満たす $ 1\le i\le N $ が存在する - 入力はすべて整数