题目描述

有一实数序列 $A[1],A[2],A[3], \sim, A[n-1],A[n]$，若 $i<j$，并且 $A[i]>A[j]$，则称 $A[i]$ 与 $A[j]$ 构成了一个逆序对，求数列 $A$ 中逆序对的个数。 例如，5 2 4 6 2 3 2 6，可以组成的逆序对有: （5 2），（5 4），（5 2），（5 3），（5 2）， （4 2），（4 3），（4 2）， （6 2），（6 3），（6 2）， （3 2） 共：12个

输入格式

共两行，第一行有一个正整数 $n$，第二行有 $n$ 个正整数。

输出格式

只有一行，为逆序对个数。

样例

输入#1

8
5 2 4 6 2 3 2 6

输出#1

12

数据范围

对于 100% 的测试数据，$n \leq 2 \times 10^5$，数组中每个数字不超过 $10^9$。