h289. 还原递增队列

题目描述

给定一个长度为 $n$ 的整数数组。每次操作可以交换一对相邻元素。求把数组变为非降序所需的最少交换次数。

这个次数等于数组中满足 $i<j$ 且 $a_i>a_j$ 的下标对数量。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

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

数据范围

• $1\le n\le 50000$
• $-10^9\le a_i\le 10^9$
• 答案不超过 $1249975000$

样例

5
3 1 2 2 0

7

标签：归并排序、分治、逆序对