题目描述

《统计逆序对》

【统计逆序对】 树状数组法 逆序对的定义：给定一个序列A1, ……, An。对于序列中的元素 a[i]和 a[j]，如果满足i<j 且a[i]>a[j]，则 (a[i],a[j]) 就是一个逆序对。 请你写一个程序，在尽量短的时间内，统计出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式

共2行。第一行输入一个整数n(0<n<2000)。第二行输入n个整数。

输出格式

一个整数表示逆序对个数。

样例

输入样例 1

6
5 4 2 6 3 1

输出样例 1

11

输入样例 2

4
1 2 3 4

输出样例 2

0

输入样例 3

4
4 3 2 1

输出样例 3

6

输入样例 4

5
2 2 1 1 3

输出样例 4

4