问题描述

给定长度为 $n$ 的序列 $a$，输出 $a$ 中逆序对的数量。

逆序对：对于 $1\le i< j\le n$，若 $a_i>a_j$ ，则 $<a_i,a_j>$ 为一对逆序对。

输入格式

第一行输入一个正整数 $n$。$(1\le n\le 10^5)$

第二行输入 $n$ 个正整数表示序列 $a$。$(1\le a_i\le 10^9,1\le i\le n)$

输出格式

输出一个整数，表示 $a$ 中逆序对的数量。

样例输入

8
1 4 7 2 5 7 9 2

样例输出

8