该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

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

输入格式

  第一行，一个数 $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$

  请使用较快的输入输出