COUNTINV - Count inversions in a small array

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

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

hide comments
2012-03-13 05:42:36 Andrés Mejía-Posada
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.
2012-03-13 05:42:36 hibernating
same ques already exixts....
http://www.spoj.pl/problems/INVCNT/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.