【模板】逆序对
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}对于给定的长度为 n 的数组 \{a_1,a_2,\dots,a_n\} ，求解数组中的逆序对数量。
\hspace{15pt}如果两个元素 a_i 和 a_j 满足 a_i > a_j 且 i < j ，那么我们称他们为一对逆序对。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left( 1 \leqq n \leqq 5 \times 10^5 \right) 代表数组中的元素数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( -10^9 \leqq a_i \leqq 10^9 \right) 代表初始数组。

输出描述:

\hspace{15pt}在一行上输出一个整数代表数组的逆序对数数量。
示例1

输入

复制 
6
1 1 4 5 1 4

输出

复制 
3

说明

\hspace{15pt}在这个样例中，一共有如下三对逆序对：\texttt{<}a_3,a_5\texttt{>} 、\texttt{<}a_4,a_5\texttt{>} 和 \texttt{<}a_4,a_6\texttt{>} 。