#include <iostream>
#include <vector>

using namespace std;

//This procedure is very similar to the merge procedure except it counts the inversions also
//arrays to be merged are arr[first:second-1] and arr[second:last]
int mergeAndCount(vector<int> & arr, int first, int second, int last)
{
	vector<int> temp; //temporary array to store merged elements
	int i = first, j = second;
	int invCount = 0;
	while( i < second && j <= last )
	{
		//If inversion is possible
		if( arr[i] > arr[j] )
		{
			//crucial step; understand carefully
			//If current element in right is less than that of left, 
			//then it is also less than all the elements to the right of it hence (second-i) inversions
			invCount += second - i; 
			temp.push_back( arr[j] );
			j++;
		}
		else
		{
			temp.push_back( arr[i] );
			i++;
		}
	}
	//Fill the temp array with left overs
	while( i < second )
	{
		temp.push_back( arr[i++] );
	}

	while ( j <= last )
	{
		temp.push_back( arr[j++] );
	}
	//copy temp elements back to the original 
	copy( temp.begin(), temp.end(), arr.begin()+first);

	return invCount;
}

//this procedure is similar to the sort procedure in merge sort
int sortAndCount( vector<int>& arr, int low, int high )
{
	//If less than two elements
	if( low >= high )
		return 0;

	int mid = low + (high-low)/2;
	int lic = sortAndCount( arr, low, mid );
	int ric = sortAndCount( arr, mid+1, high);
	int ic = mergeAndCount( arr, low, mid+1, high);
	return lic+ric+ic;
}
int getInversionCount(vector<int>& arr )
{
	if( arr.size() > 0 )
		return sortAndCount( arr, 0, arr.size()-1 );
	return 0;
}
void Test1()
{
	//Random test case
	int nums[] = { 3, 1, 2, 5, 4 };
	vector<int> arr( nums, nums+5 );
	cout << getInversionCount( arr) << endl;
}

void Test2()
{
	//No inversion
	int nums[] = { 1, 2, 3, 4, 5 };
	vector<int> arr( nums, nums+5 );
	cout << getInversionCount( arr) << endl;
}

void Test3()
{
	//Every pair is an inversion
	int nums[] = { 5, 4, 3, 2, 1 };
	vector<int> arr( nums, nums+5 );
	cout << getInversionCount( arr) << endl;
}

void Test4()
{
	//Just a single element
	int nums[] = { 1 };
	vector<int> arr( nums, nums+1 );
	cout << getInversionCount( arr) << endl;
}

void Test5()
{
	//one more random test case
	int nums[] = { 2, 1, 4, 3, 6, 5 };
	vector<int> arr( nums, nums+6 );
	cout << getInversionCount( arr) << endl;
}
int main()
{
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();
	return 0;
}