COUNTINV - Count inversions in a small array

no tags 

Given a 0-indexed array A of n integers we define an inversion as a pair of integers (ij) such that 0 <= i < j < n and A[i] >A[j].

In this problem, you will be given an array and your task is to calculate the total number of inversions in this array.

Input

The input consists of several test cases.

Each test case is described in two lines. The first line contains n, the size of the array (1 <= n <= 1000). The second line contains the array: n integers separated by one or more spaces. Each integer in the array will be between -109 and 109, inclusive.

Output

For each test case, write the total number of inversions of the array on a single line.

Example

Input:
2
1 2
3
3 2 1
4
0 0 0 0
5
1 2 3 5 4
6
3 1 6 5 2 4
10
5 2 10 8 1 9 4 3 6 7
0

Output:
0
3
0
1
7
22

hide comments
Andrés Mejía-Posada: 2012-03-13 05:42:36

It's not exactly the same problem. This one is easier, an O(n^2) solution should be enough to pass.

I've moved this problem to Tutorial.

hibernating: 2012-03-13 05:42:36

same ques already exixts....
http://www.spoj.pl/problems/INVCNT/


Added by:Andrés Mejía-Posada
Date:2012-03-12
Time limit:0.211s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Introduction to Programming Course, EAFIT University