You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

排序（$\texttt{sort}$）

【题目描述】

小 D 有一个数列 $a_1\sim a_n$，他可以对这个数列进行若干次操作，每次操作可以选择一个 $1\sim n-1$ 中的 $i$，然后交换 $a_i,a_{i+1}$。

小 D 还可以在操作前使用一次超能力，他可以任选两个下标 $i,j$ 满足 $1\le i<j\le n$，然后交换 $a_i,a_j$。

小 D 想知道使用一次超能力后（不能不使用），至少要多少次操作才能把 $a_1\sim a_n$ 变成不降的。

【输入格式】

从 $\texttt{sort.in}$ 中读入数据。

第一行一个整数 $n$。

接下来 $n$ 行，每行一个整数，第 $i$ 个整数表示 $a_i$。

【输出格式】

输出到 $\texttt{sort.out}$ 中。

一行一个整数表示最小操作次数。

【样例 1 输入】

5
3
1
7
9
5

【样例 1 输出】

2

【样例 1 解释】

先用超能力交换 $a_3,a_5$，得到序列 $a=[3,1,5,9,7]$，交换 $a_1,a_2$，交换 $a_4,a_5$。

【样例 2 输入】

3
1
2
3

【样例 2 输出】

1

【样例 2 解释】

不能不使用超能力。

【样例 3】

见下发文件中的 $\texttt{sort3.in}$ 与 $\texttt{sort3.ans}$。

该样例满足子任务 $2$ 的限制。

【样例 4】

见下发文件中的 $\texttt{sort4.in}$ 与 $\texttt{sort4.ans}$。

该样例满足子任务 $4$ 的限制。

【数据范围】

对于所有的测试数据有：$2\le n\le 10^5,1\le a_i\le 10^9$。