题目描述

给定一个数字序列 $a_1,a_2,\cdots,a_n$ 的逆序对是满足 $i<j$ 且 $a_i>a_j$ 的对数。

对于给定的数字序列 $a_1,a_2,\cdots,a_n$ ，如果我们将前 $m$ 个数字移动到序列的末尾（$m \ge 0$），我们将得到另一个序列。共有 $n$ 种这样的序列，如下所示：

$a_1,a_2,\cdots,a_{n-1},a_n$（其中 $m=0$ 为初始序列） $a_2,a_3,\cdots,a_{n},a_1$（其中 $m=1$） $a_3,a_4,\cdots,a_{1},a_2$（其中 $m=2$） $\cdots$ $a_n,a_1,\cdots,a_{n-2},a_{n-1}$（其中 $m=n-1$）

请编写一个程序，找出上述序列中逆序对数量最小的那个。

输入格式

每个用例包括两行：第一行包含一个正整数 $n$；

接下来一行包含从 $0$ 到 $n-1$ 的 $n$ 个整数的排列。

输出格式

对于每个用例，输出一个单独的行，包含逆序数最小的值。

10
2 1 3 6 9 0 8 5 7 4 

16

样例分析

数列 $\{1,3,6,9,0,8,5,7,4,2\}$ 的逆序对数量是 $22$；

数列 $\{3,6,9,0,8,5,7,4,2,1\}$ 的逆序对数量是 $29$；

数列 $\{6,9,0,8,5,7,4,2,1,3\}$ 的逆序对数量是 $32$；

数列 $\{9,0,8,5,7,4,2,1,3,6\}$ 的逆序对数量是 $20$；

数列 $\{0,8,5,7,4,2,1,3,6,9\}$ 的逆序对数量是 $20$；

数列 $\{8,5,7,4,2,1,3,6,9,0\}$ 的逆序对数量是 $29$；

数列 $\{5,7,4,2,1,3,6,9,0,8\}$ 的逆序对数量是 $22$；

数列 $\{7,4,2,1,3,6,9,0,8,5\}$ 的逆序对数量是 $21$；

数列 $\{4,2,1,3,6,9,0,8,5,7\}$ 的逆序对数量是 $16$；

数列 $\{2,1,3,6,9,0,8,5,7,4\}$ 的逆序对数量是 $17$；

数据范围与提示

对于 $100\%$ 数据：$1 \le n \leq 5 \times 10^3$。