题目描述

给定一个数列 $a$，这个数列满足（$a_i\neq a_j$），现在要求你把这个数列从小到大排序，每次允许你交换其中连续两个数，请问最少需要几次交换？

输入

第一行是一个整数，代表数字个数 $n$。第二行有 $n$ 个整数用空格分隔开，表示数列 $a$ 。

输出

只有一行，包含一个数，表示最少的交换次数。

样例

8
8 23 4 16 77 -5 53 100

9

提示

对于$100\%$的数据，保证$1\leq n\leq3*10^3$

$-10^9<=a_i<=10^9$