逆序对计数 · 进阶版

题目描述

给定一个长度为 n 的整数序列 a。

如果存在 i < j 且 a[i] > a[j]，则称 (i,j) 为一个逆序对。

请计算序列中的逆序对数量。

输入格式

第一行输入一个整数 n。

第二行输入 n 个整数 a[i]。

输出格式

输出逆序对数量。

样例

输入

6
7 3 5 1 6 2

输出

10

数据范围

• 1 <= n <= 2 * 10^5
• 0 <= a[i] <= 10^9

提示

O(n^2) 的二重循环只能解决较小数据。要通过全部测试点，需要把复杂度降到约 O(n log n)。