计点交换

盲区驱散了，但Echo-0的信息迷宫里还有一个计数问题——交换。

"交换？"CC问。

"对。"你说，"给定一个排列，每次可以交换相邻两个元素。求把它变成有序的最少交换次数。"

"最少？"

"对。"你说，"这就是逆序对个数——每个逆序对至少要交换一次。"

"逆序对？"

"对。"你说，"如果$i<j$但$a_i>a_j$，就是一个逆序对。"

"咋算？"

"树状数组或归并排序。"你说，"$O(n\log n)$。"

"树状数组？"

"对。"你说，"从左到右扫描，查询之前比当前元素大的个数，累加起来。"

"第47个元素。"你说，"值为47——它前面有46个元素，都比它小，所以没有逆序对。"

"那47后面呢？"

"如果后面有比47小的，就有逆序对。"你说，"但如果没有——逆序对就是0。"

"简单。"

"对。"你说，"但整个排列的逆序对可能很多。"

"最多多少？"

"$n(n-1)/2$。"你说，"完全逆序的排列。"

"$47\times 46/2=1081$。"

"对。"你说，"1081次交换。"

CC数了数——1081。

"好多。"她说。

"对。"你说，"但我们可以一步步来。"

"一步多少？"

"一次交换解决一个逆序对。"你说，"1081步，就是有序。"

"像整理房间。"

"对。"你说，"像整理房间——乱的东西，一件一件归位。"

Echo看着交换的过程——像洗牌，像整理记忆，像某种失序的东西重新排列。

"以前我的记忆是乱的。"她说，"现在……在归位。"

"因为有我们帮你。"你说。

"对。"她说，"因为有你们。"

题目描述

给定一个$1$到$n$的排列，求逆序对个数（最少相邻交换次数）。

输入格式

第一行$n$。第二行$n$个整数。

输出格式

逆序对个数。

输入样例

5

输出样例

1
1
1
1
1

提示

• 树状数组或归并排序求逆序对。
• 树状数组：扫描时查询$[a_i+1,n]$的和。
• 时间复杂度$O(n\log n)$。