描述

给定一个长度为 $n$ 的序列 $A$，求将该序列排序所需的最少交换次数。每次只能交换相邻的两个元素。

最少交换次数即为在排序过程中，每次交换相邻两个元素的位置直到序列排序完成。

格式

输入

• 第一行包含一个整数 $n$ ($1 \leq n \leq 10^5$)。
• 第二行包含 $n$ 个整数 $A[1], A[2], \dots, A[n]$ ($|A[i]| \leq 10^9$)。

输出

• 输出一个整数，表示最少交换次数。

样例

输入1

5
2 3 8 6 1

输出1

5

限制

• 时间限制：1s