问题背景

我们称一个长度为 $n$ 的数列是一个排列，当且仅当整数 $1, 2, \ldots, n$ 在排列中均恰好出现一次。比如：

• 数列 $\{ 1, 3, 2 \}$，$\{ 5, 3, 1, 4, 2, 6 \}$ 都是排列；
• 数列 $\{ 1, 1, 2 \}$，$\{ 1, 2, 4, 3, 6 \}$ 都不是排列。

题目描述

给你一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，求排列的逆序对数量。

输入格式

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

第二行，$n$ 个整数 $p_1, p_2, \ldots, p_n$，表示一个长度为 $n$ 的排列。

输出格式

输出一个整数，表示排列 $p$ 的逆序对数。

样例

8
5 7 3 2 1 6 8 4

14

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 50$
• 对于 $50\%$ 的数据，$n \le 5000$
• 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，且数列 $p_1, p_2, \ldots, p_n$ 是一个大小为 $n$ 的排列