对于一个数列 $A_1,A_2,...,A_n$ 来说，若存在 $A_i,A_j$ ，满足 $i \lt j且A_i \gt A_j$ 则称这一对数为一个逆序对，一个数列的逆序对数即该数列逆序对的总数。

对于一个数列 $A_1,A_2,...,A_n$ ，我们可以通过每次将第一个数移到数列的末尾来形成一个新的数列，这样可以形成的数列共有 $n$ 个

$A_2,A_3,...,A_n,A_1$

$A_3,A_4,...,A_1,A_2$

...

$A_n,A_1,...,A_{n-2},A_{n-1}$

$A_1,A_2,...,A_{n-1},A_n$

现在请你找出以上所有数列的逆序对数中最小的那一个。

输入格式

输入有多组数据，请处理至文件末尾

每组数据的第一行为一个整数 $n$ ，表示数列长度

第二行为 $n$ 个整数，依次表示 $A_1,A_2,...,A_n$

输出格式

对于每组数据，输出一行一个整数，即为题意中所求答案

样例

样例输入

10
1 3 6 9 0 8 5 7 4 2

样例输出

16

数据范围与提示

• 对于$30$%数据 $n \leq 50$
• 对于$60$%数据 $n \leq 500$
• 对于$100$%数据 $n \leq 5000$
• 对于所有数据，$A_i \leq 10^9$，数据组数 $\le 100$

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$32768\mathrm{KB}$