问题描述

给定 $n$ 个整数，求其中逆序对的个数。

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

输入格式

第一行包含一个整数 $n$，表示数字的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，用空格隔开。

输出格式

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

样例输入 1

5
1 2 3 4 5

样例输出 1

0

样例输入 2

5
5 4 3 2 1

样例输出 2

10

样例输入 3

3
3 1 2

样例输出 3

2

评测数据规模

• $1 \le n \le 100$
• $1 \le a_i \le 100$