题目描述

给定一个长度为$n$的数组，需要你去计算这个数组的逆序对的数量。

逆序对定义：对于数组中两个位置分别为$i,j$的元素$w[i],w[j]$，如果有$i<j$并且$w[i]>w[j]$，则称这对$(i,j)$为一个逆序对。

例如，数组$w=[1,3,4,2,5]$，其中3和2就是构成了一个逆序对。

输入描述

第一行包含一个正整数 $n(1\le n\le 10^5)$，分别表示该数组的长度

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数组第 $i$ 个元素的值。$(1\le w[i]\le 10^5)$

输出描述

输出一个整数，表示该数组的逆序对数量。

样例

输入

5
3 2 1 5 4

输出

4