塔子哥是一个程序员,他正在为一个新的项目编写代码。这个项目需要对一个数组进行操作,但是这个数组的初始值不满足项目的要求。于是,塔子哥想到了一个办法:他可以修改数组中的任意一个元素,将其修改为任意值。他希望用最少的操作方式使得数组满足以下条件:
最终数组仍是一个排列。
最终数组的逆序对数量为 1 。
数组的逆序对是指,满足 i<j 且 ai>aj 的二元组数量。
排列指长度为 n 的数组, 1 到 n 每个正整数恰好出现 1 次。
第一行输入一个正整数 n ,代表数组的大小。
第二行输入 n 个正整数 ai ,代表塔子哥拿到的数组。
2≤n≤105
1≤ai≤n
保证初始数组是一个排列。
一个整数,代表最小的操作次数。
输入
4
3 2 1 4
输出
3
样例解释
将数组修改为 [2,1]
即可。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.