冒泡排序

题目描述

小X学习了冒泡排序算法——给定一个长度为 $N$ 的序列 $a_1, a_2, a_3, \ldots, a_N$，如果要将这个序列中的数字从小到大排列，就需要依次比较相邻两个数字的大小，当相邻数字中前一个数字比后一个数字大时，则应交换这两个数字的位置，重复这些操作就能完成对应的排序任务。

小X发现冒泡排序算法中，相邻元素的交换次数是可以被提前计算的。如果序列中的两个数字 $a_i$ 与 $a_j$，满足 $i < j$ 且 $a_i > a_j$，这两个数字就可以被称作是一个逆序对。有意思的是，如果用冒泡排序算法将给定序列 $a_1, a_2, a_3, \ldots, a_N$ 中的数字从小到大排列，算法所需的相邻元素的交换次数正好等于这个序列中的逆序对个数。

现在请你计算：如果使用冒泡排序算法将给定序列 $a_1, a_2, a_3, \ldots, a_N$ 中的数字从小到大排列，那么算法所需的相邻元素的交换次数到底是多少？

输入格式

第一行包括一个整数 $N$，表示序列的长度。

第二行包括 $N$ 个整数 $a_1, a_2, a_3, \ldots, a_N$，依次表示序列中每一项元素。

输出格式

一个整数，表示对于给定序列，冒泡排序算法所需的相邻元素的交换次数。

样例 #1

样例输入 #1

5
1 5 2 3 4

样例输出 #1

3

样例 #2

样例输入 #2

5
4 4 2 3 1

样例输出 #2

8

提示

【输入输出】

样例#2中，序列共包括 $8$ 个逆序对，其中 ${4, 2}$、${4, 3}$ 和 ${4, 1}$ 各两对，以及 ${2, 1}$ 和 ${3, 1}$ 各一对，因此对于该序列进行冒泡排序，共会执行 $8$ 次相邻元素的交换。

【数据规模与约定】

对于 20% 的数据，$1 ≤ N ≤ 100$，$0 ≤ a_i ≤ 100$，且 $a_i$ 两两不同。

对于 40% 的数据，$1 ≤ N ≤ 5000$，$0 ≤ a_i ≤ 100$。

对于 70% 的数据，$1 ≤ N ≤ 100000$，$0 ≤ a_i ≤ 100$。

对于 100% 的数据，$1 ≤ N ≤ 100,000$，$|a_i| ≤ 100$。