#H17. 【拓展题】逆序对

【拓展题】逆序对

背景

  基于归并排序,求解给定数组的逆序对问题

输入格式

  第一行,一个数 nn,表示序列中有 nn个数。

  第二行 nn 个数,表示给定的序列。序列中每个数字不超过 10910^9

输出格式

  输出序列中逆序对的数目。

样例 #1

样例输入 #1

6
5 4 2 6 3 1

样例输出 #1

11

提示

  对于 25%25\% 的数据,n2500n \leq 2500

  对于 50%50\% 的数据,n4×104n \leq 4 \times 10^4

  对于所有数据,n5×105n \leq 5 \times 10^5

  请使用较快的输入输出