## 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
``` 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/