题目描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。
对于不同的排名结果可以用逆序来评价它们之间的差异。考虑 $1,2,\dots,n$ 的排列 $i_1,i_2,\dots,i_n$，如果其中存在 $j,k$，满足 $j \lt k$ 且 $i_j \gt i_k$，那么就称 $(i_j, i_k)$ 是这个排列的一个逆序。
一个排列含有逆序的个数称为这个排列的逆序数。例如排列 $2,6,3,4,5,1$ 含有 $8$ 个逆序：$(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)$，因此该排列的逆序数就是 $8$。显然，由 $1,2,\dots,n$ 构成的所有 $n!$ 个排列中，最小的逆序数是 $0$，对应的排列就是 $1,2,\dots,n$；最大的逆序数是 $\frac{n(n-1)}{2}$，对应的排列就是 $n,n-1,\dots,2,1$。逆序数越大的排列与原始排列的差异度就越大。
现给定 $1,2,…,n$ 的一个排列，求它的逆序数。