排列记忆

曲线抹平了，但记忆是排列的——需要重新排列。

"排列？"CC问。

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

"有序？"

"对。"你说，"从小到大。"

"交换？"

"对。"你说，"只能交换相邻的。"

"咋算？"

"逆序对。"你说，"每个逆序对至少需要交换一次。"

"逆序对？"

"对。"你说，"$i<j$但$a_i>a_j$。"

"咋数？"

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

"第47个数。"你说，"值为47——如果前面有比它大的，就有逆序对。"

"多少？"

"看前面有多少个比47大的。"你说，"如果序列是$47,46,\dots,1$，有46个逆序对。"

"最多？"

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

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

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

CC看着序列——像一排人，像一队兵，像某种需要整理的东西。

"整理？"她问。

"对。"你说，"把乱的变成有序的。"

"咋整？"

"一步一步换。"你说，"每次换相邻两个，慢慢排好。"

"慢吗？"

"对。"你说，"但稳定——每次只动一点点。"

"像整理房间。"

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

Echo把交换过程投射出来——数字一跳一跳，像跳舞，像心跳。

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

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

"对。"她说，"因为你们在帮我。"

题目描述

给定$1$到$n$的排列，求变成有序的最少相邻交换次数。

输入格式

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

输出格式

最少交换次数。

输入样例

5
1 2 3 4 5

输出样例

0

提示

• 逆序对个数就是答案。
• 树状数组或归并排序求逆序对。
• 时间复杂度$O(n\log n)$。