#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

void PrintVector( const vector<int> & arr )
{
	for( unsigned int i = 0; i < arr.size(); ++ i )
	{
		cout << arr[i] << ", ";
	}
	cout << endl;
}

void ReadArray( vector<int> & arr )
{
	ifstream arrfile("IntegerArray.txt");
	int a;
	while( arrfile >> a )
	{
		arr.push_back( a );
	}
}

unsigned long int DumbInversions( const vector<int> & arr )
{
	unsigned long int result = 0;
	for( unsigned int i = 0; i < arr.size() - 1; ++ i )
	{
		for( unsigned int j = i + 1; j < arr.size(); ++ j )
		{
			if( arr[i] > arr[j] )
				result ++;
		}
	}
	return result;
}

unsigned long MergeSortInversions(
	const vector<int> & in,
	int from, int to,
	vector<int> & out
	)
{
	int diff = to - from;
	if( diff == 0 )
	{
		out.push_back( in[from] );
		return 0;
	}
	if( diff == 1 )
	{
		if( in[from] < in[to] )
		{
			out.push_back( in[from] );
			out.push_back( in[to] );
			return 0;
		}
		else
		{
			out.push_back( in[to] );
			out.push_back( in[from] );
			return 1;
		}
	}
	
	int div = (from + to) / 2;
	vector<int> arr_left;
	unsigned long inv_left = MergeSortInversions( in, from, div, arr_left );
	vector<int> arr_right;
	unsigned long inv_right = MergeSortInversions( in, div+1, to, arr_right );
	unsigned int r = 0;
	unsigned int l = 0;
	unsigned long invs = 0;
	for( int i = 0; i <= diff; ++ i )
	{
		if( l >= arr_left.size())
		{
			out.push_back( arr_right[r] );
			r ++;
			continue;
		}
		if( r >= arr_right.size())
		{
			out.push_back( arr_left[l] );
			l ++;
			continue;
		}
		if( arr_left[l] < arr_right[r])
		{
			out.push_back( arr_left[l] );
			l ++;
		}
		else
		{
			out.push_back( arr_right[r] );
			r ++;
			invs += arr_left.size() - l;
		}
	}
	return inv_left + inv_right + invs;
}

unsigned long MergeSortInversions( const vector<int> & arr )
{
	vector<int> sorted;	
	unsigned long int invs = MergeSortInversions( arr, 0, arr.size()-1, sorted);
	return invs;
}

int main( /*int argc, char * argv[]*/ )
{
	vector<int> arr;
	ReadArray( arr );
	unsigned long int good_result = 2407905288;
	cout <<  good_result << endl;
	cout << "Array of " << arr.size() << " elements." << endl;
	//unsigned long int dumb_inv = DumbInversions( arr );
	//cout << "Dumb inv: " << dumb_inv << endl;
	unsigned long int merge_inv = MergeSortInversions( arr );
	cout << "Merge inv: " << merge_inv << endl;
	return 0;
}