题目描述

在排列 a 中，其 1, 2, …, n 的位置对应的值为 a₁, a₂, …, a_n。如果其中存在 j, k，满足 j < k 且 a_j > a_k，那么就称 (a_j, a_k) 是这个排列的一个逆序对。

一个排列含有逆序对的个数称为这个排列的逆序数。例如排列 263451 含有 8 个逆序对：(2,1)、(6,3)、(6,4)、(6,5)、(6,1)、(3,1)、(4,1)、(5,1)，因此该排列的逆序数就是 8。

现给定一个排列，求它的逆序数。

输入格式

第一行是一个整数 n，表示该排列有 n 个数（n ≤ 100000）。

第二行是 n 个不同的正整数，之间以空格隔开，表示该排列。

输出格式

输出该排列的逆序数。

输入样例 #1

6  
2 6 3 4 5 1

输出样例 #1

8