题目描述

树状数组+离散化 逆序对的定义：给定一个序列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

1
0

输出样例 2

0

输入样例 3

2
2 1

输出样例 3

1