1246 - 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.