Description

设A[1..n]是一个包含N个数的数组。如果在i<j的情况下，有A[i]>A[j]，则(i,j)就称为A中的一个逆序对。 例如，数组（3，1，4，5，2）的“逆序对”有 ＜3,1＞,＜3,2＞,＜4,2＞,＜<5,2＞ 共4个。 使用 归并排序 可以用O(nlogn)的时间解决统计逆序对个数的问题 。

Format

Input

第1行：1个整数N表示排序元素的个数。(1≤N≤100000) 第2行：N个用空格分开的整数，每个数在小于100000

Output

1行：仅一个数，即序列中包含的逆序对的个数

Samples

3
1 3 2

1