inversion pair II
Time Limit : 3 Second
Memory Limit : 128 MB
Submission: 377
Solved: 84
- Description
- An pair ( i , j ) is called ‘inversion pair’ if and only if i < j and a[i] > a[j].
Given an integer sequence {a[i]} with N elements ( 1 <= N <= 100000 ), output the total number of inversion pairs.
A integer sequence like this : 2, 3, 1 has two inversion pairs.( 2, 1) and (3, 1)
- Input
- The input contains several test cases.
Each case begins with a number N ( 1 <= N <= 100000 ) , then N integers followed . - Output
- The number of the sequence's inversion pairs in the input.
- sample input
-
3 3 2 1 2 1 2
- sample output
-
3 0
- hint
- source