← 返回题目列表

AtCoder · abc436_e

H. 最小掉期

中文机器翻译题面 查看原题

分数: 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