This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.

Tips:

If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.

Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

**Eg: **The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

You can get working program from here

Input files : Input1 Input2

Answer for input1 :

Answer for input 2: 25

### Like this:

Like Loading...

*Related*