题目描述

给定一个长度为 $n$ 的整数序列 $a$，求它的逆序对个数。

若 $i<j$ 且 $a_i>a_j$，则称 $(i,j)$ 是一个逆序对。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，表示序列 $a$。

输出格式

一个整数，表示逆序对个数。

输入输出样例 #1

输入 #1

5
5 4 3 2 1

输出 #1

10

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times10^5$，$|a_i|\le 10^9$。完全逆序的 $2\times10^5$ 个元素约有 $2\times10^{10}$ 个逆序对。