分数: 475 点
问题陈述
给你一个整数序列 给出了 P=(P _ 1,P _ 2,\ldots,P _ N) 这是一个排列 (1,2,\ldots,N)。 在此,可以保证 P 不等于 (1,2,\ldots,N).
您想要执行以下操作零次或多次以使得 P 匹配序列 (1,2,\ldots,N):
- 选择一对整数 (i,j) 满意 1\le i\lt j\le N。交换以下值 P _ i 和 P _ j.
让 K 是进行操作所需的最少操作数 P 匹配序列 (1,2,\ldots,N).
找出可以进行的操作数 第一次操作 在一系列操作中,使得 P 匹配序列 (1,2,\ldots,N) in K 操作。 区分两个运算当且仅当所选的整数对 (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)
- 存在 1\le i\le N 这样 i\ne P _ i.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P _ 1 P _ 2 \ldots P _ N
输出
打印答案。
示例输入 1
5 3 1 4 2 5
示例输出 1
6
例如,可以通过以下三个操作来实现目标:
- 选择 (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).
该目标无法通过两次或更少的操作来实现,因此 K=3.
如上所述,选择 (1,2) 第一个操作允许通过三个操作实现目标。 此外,如果其中之一 选择 (1,3),(1,4),(2,3),(2,4),(3,4) 作为第一个操作,然后适当地执行接下来的两个操作, 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