题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$，如果存在 $i＜j$ 并且 $a_i＞a_j$，那么我们称 $(a_i,a_j)$ 为逆序对。

一个排列含有逆序对的个数称为这个排列的逆序数。

例如排列 $263451$ 含有 $8$ 个逆序对：$(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)$，

因此该排列的逆序数就是 $8$ 。

现给定 $1,2,…,n$ 的一个排列，求它的逆序数。

输入格式

第一行是一个整数 $n$，表示该排列有 $n$ 个数 $（n ≤ 100000)$ 。

第二行是 $n$ 个不同的正整数，之间以空格隔开，表示该排列。

输出格式

输出该排列的逆序数。

6
2 6 3 4 5 1

8