题目描述

给定一个长度为 $N$ 的序列 $A$，如果对于下标 $i < j$ 且 $A[i] > A[j]$，那么我们称 $(i, j)$ 为一个逆序对。 请求出序列中逆序对的总数。

输入格式

第一行 $N$ ($1 \le N \le 5 \times 10^5$)。 第二行 $N$ 个整数。

输出格式

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

样例

6
5 4 2 6 3 1

11

样例解释

• 序列为 $5, 4, 2, 6, 3, 1$。
• 逆序对包括：(5,4), (5,2), (5,3), (5,1), (4,2), (4,3), (4,1), (2,1), (6,3), (6,1), (3,1)。共 11个