/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
(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) が異なるとき、またそのときに限り区別します。
制約
- 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 が存在する
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P _ 1 P _ 2 \ldots P _ N
出力
答えを出力せよ。
入力例 1
5 3 1 4 2 5
出力例 1
6
例えば、次のようにして 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 を出力してください。
入力例 2
2 2 1
出力例 2
1
入力例 3
20 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
出力例 3
77
Score : 475 points
Problem Statement
You are given an integer sequence P=(P _ 1,P _ 2,\ldots,P _ N) that is a permutation of (1,2,\ldots,N). Here, it is guaranteed that P is not equal to (1,2,\ldots,N).
You want to perform the following operation zero or more times to make P match the sequence (1,2,\ldots,N):
- Choose a pair of integers (i,j) satisfying 1\le i\lt j\le N. Swap the values of P _ i and P _ j.
Let K be the minimum number of operations required to make P match the sequence (1,2,\ldots,N).
Find the number of operations that can be the first operation in a sequence of operations that makes P match the sequence (1,2,\ldots,N) in K operations. Two operations are distinguished if and only if the chosen pairs of integers (i,j) are different.
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)
- There exists 1\le i\le N such that i\ne P _ i.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P _ 1 P _ 2 \ldots P _ N
Output
Print the answer.
Sample Input 1
5 3 1 4 2 5
Sample Output 1
6
For example, the goal can be achieved in three operations as follows:
- Choose (i,j)=(1,2). P becomes (1,3,4,2,5).
- Choose (i,j)=(2,4). P becomes (1,2,4,3,5).
- Choose (i,j)=(3,4). P becomes (1,2,3,4,5).
The goal cannot be achieved in two or fewer operations, so K=3.
As explained above, choosing (1,2) for the first operation allows the goal to be achieved in three operations. Additionally, if one of (1,3),(1,4),(2,3),(2,4),(3,4) is chosen for the first operation, then by performing the next two operations appropriately, P can be made equal to (1,2,3,4,5).
Therefore, print 6.
Sample Input 2
2 2 1
Sample Output 2
1
Sample Input 3
20 15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1
Sample Output 3
77