题目描述

给定一段正整数序列 $a_1,a_2,\ldots,a_n$，求出其中的逆序对个数。

逆序对定义：对于一对下标 $\{i,j\}$，满足

• $a_i > a_j$
• $i < j$

输入格式

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

第二行 $n$ 个数，表示给定的序列 $a_1,a_2,\ldots,a_n$

输出格式

给定序列中逆序对的数目。

6
5 4 2 6 3 1

11

数据范围

$1 \le n \le 500000$

$-2^{31} \le a_i < 2^{31}$