题目描述

对于给定的一段正整数序列,逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。
给定的一段正整数序列,求逆序对的数目。
注意答案用int可能会爆,请使用long long统计。


输入格式

第一行,一个数 n,表示序列中有 n个数。
第二行 n 个数,表示给定的序列。序列中每个数字不超过$1\leq a_i \leq n$。


输出格式

一行一个整数表示答案。


样例数据

输入

6
5 4 2 6 3 1

输出

11

备注

$n\leq 5\times 10^5,\ 1\leq a_i \leq n$


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务