You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

背景

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

输入格式

  第一行，一个数 $n$，表示序列中有 $n$个数。

  第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

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

样例 #1

样例输入 #1

6
5 4 2 6 3 1

样例输出 #1

11

提示

  对于 $25\%$ 的数据，$n \leq 2500$

  对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

  对于所有数据，$n \leq 5 \times 10^5$

  请使用较快的输入输出