Background

Special for beginners, ^_^

Description

给定一个序列 $a_1,a_2,…,a_n$，如果存在 $i<j,a_i>a_j$，那么我们称之为逆序对，求 $a$ 中逆序对的数目。

Format

Input

第一行为 $n$，表示序列长度，接下来的 $n$ 行，第 $i+1$ 行表示序列中的第 $i$ 个数。

Output

$a$ 中逆序对的数目。

Samples

4
3
2
3
2

3

Limitation

1s, 1024KiB for each test case.

$N≤10^5，A_i≤10^5$。