题目描述

逆序对是指在一个序列中，如果存在两个元素满足前面的元素大于后面的元素，且前面的元素在序列 中的位置在后面的元素之前，那么这两个元素就构成一个逆序对。具体来说，对于序列中的元素 a[i]和 a[j]， 如果满足i<j 且a[i]>a[j]，则 (a[i],a[j]) 就是一个逆序对。?请求出整数序列A的所有逆序对个数。

输入格式

共2行。第一行输入一个整数n(0<n<1000)。第二行输入n根柱子的高度。

输出格式

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

样例

输入样例 1

6
9 7 5 8 3 10

输出样例 1

8

输入样例 2

5
1 2 3 4 5

输出样例 2

0

输入样例 3

4
4 3 2 1

输出样例 3

6

输入样例 4

6
5 2 3 2 1 4

输出样例 4

9