^{2}). But submitting this solution will lead to TLE (time limit exceeded). So we need to use some other algo, and the solution uses Merge Function in Merge Sort Algorithm. Actually when we merge the two sorted array, while comparing elements we can perform the counting of inversion pairs. This can be done as : (for ascending order sorting) When the current element under consideration in right sub-array is smaller than current element under consideration in left sub-array the no of inversion pairs equals to the no. of all the elements after the current element in left sub-array (including itself), in each level of merge sort. Sum of all these pairs will be equal to inversion pairs. This can be understood using following : Here is the following pseudo-code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <iostream>
typedef long long int typex;
using namespace std;
long long int count,arr[200001];
void merge(typex p,typex q,typex r)
{
//first array has indices from p to q
//second array has indices from q to p
typex i,li,ri,n1,n2;
n1=q-p+1;
n2=r-q;
typex *lt= new typex [n1];
typex *rt= new typex [n2];//[q-(r+1)+1]
// HERE copy both the arrays in the newly dynamically allocated array.
//left and right array is ready which is all ready sorted
//now we will merge
//indices fr left copy and right copy respectively
li=ri=0;
i=p;//index for array being sorted
while(li< n1 && ri< n2)
{
if(lt[li]> rt[ri])
{
arr[i++]=rt[ri++];
count=count+n1-li;// MAIN STEP
}
else //right hand side elemnt is greater that is inversion pair
{
arr[i++]=lt[li++];
}
}
//inversion pairs have been counted till this stage, do not count again;
while(li<n1)
arr[i++]=lt[li++];
while(ri<n2)
arr[i++]=rt[ri++];
}
void mergesort(typex p,typex r)
{
if(p<r)
{
typex q=(p+r)/2;
mergesort(p,q);
mergesort(q+1,r);
}
}
int main()
{
////Write code accordingly
count=0;
mergesort(0,n-1);
cout<<"\n"<<count;
////
}