题目描述

给定一个$1$到$n$的排列$a_i$，求逆序对个数。

一个逆序对是指，$i<j$且$a_i>a_j$。

输入格式

第一行输入一个整数$n$； 第二行输入$n$个整数$a_i$，表示一个$1$到$n$的排列。

输出格式

输出一个整数，表示你的答案。

样例输入 #1

6
5 4 2 6 3 1

样例输出 #1

11

说明/提示

对于30%的数据，有$1\leq n\leq 10^3$； 对于100%的数据，有$1\leq n\leq 5\times 10^5$。