Coding is the closest thing we have to a surperpower

3640 : 树状数组-逆序对
描述

对于给定的一段正整数序列,逆序对就是序列中 a_i>a_j​ 且 i < j 的有序对。

算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入

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

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

对于 40% 的数据,n \leq 2500

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

输出

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

样例

输入

6
5 4 2 6 3 1

输出

11
标签
语言:
主题: