#P17929. Increasing Swaps
Increasing Swaps
Increasing Swaps
给定 的排列 。你可以选择一个长度为 的正整数序列 。
操作从第 次开始编号。在第 次操作中,将所有满足 的下标 按升序排列,然后依次交换 和 。同一次操作中的交换按顺序执行,后面的交换使用前面的交换完成后的排列。
对于固定的 ,定义 为使 变为升序排列所需的最少操作次数(允许为 );如果永远不能排序,则定义 。
求所有合法 中 的最小值。可以证明,题目范围内一定存在使 的 。
输入格式
N
P_1 P_2 ... P_N
输出格式
输出一个整数,表示答案。
数据范围
, 是 到 的排列。所有输入均为整数。
原比赛另设 的部分分;本数据包使用完整范围、整题计分。
样例 1
输入:
4
4 2 1 3
输出:
2
样例 2
输入:
20
15 13 7 3 4 8 16 12 2 5 1 17 11 18 9 19 20 10 6 14
输出:
39