思路

逆序对只有一对的排列只能是从1~n中交换相邻的一对，比如:1、2、3、5、4、6这样的，所以直接枚举所有的符合条件的排列即可，先计算一下原排列和1~n中相同的位置有多少，然后再枚举交换相邻的一对的位置，再特殊处理一下，过程中取最小值即可。

代码

c++

题目内容

小红是一个程序员，他正在为一个新的项目编写代码。这个项目需要对一个数组进行操作，但是这个数组的初始值不满足项目的要求。于是，小红想到了一个办法：他可以修改数组中的任意一个元素，将其修改为任意值。他希望用最少的操作方式使得数组满足以下条件：

1. 最终数组仍是一个排列。

2. 最终数组的逆序对数量为 $1$ 。

数组的逆序对是指，满足 $i \lt j$ 且 $a_i \gt a_j$ 的二元组数量。

排列指长度为 $n$ 的数组， $1$ 到 $n$ 每个正整数恰好出现 $1$ 次。

输入描述

第一行输入一个正整数 $n$ ，代表数组的大小。

第二行输入 $n$ 个正整数 $a_i$ ，代表小红拿到的数组。

$2\le n\le 10^5$

$1\le a_i\le n$

保证初始数组是一个排列。

输出描述

一个整数，代表最小的操作次数。

样例

样例一：

输入

4
3 2 1 4

输出

3

样例解释

将数组修改为 [2,1] 即可。