1428

The problem can be solved using Binary Indexed tree or Fenwick tree.

#include <cstdio>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>

#define SZ 100000+5
#define ll long long

using namespace std;

int arr[SZ];
ll Left[SZ],Right[SZ],sum[SZ];
int mx;

ll Cumulative(int idx)
{
	ll value=0;
	while(idx>0)
	{
		value += sum[idx];
		idx -= (idx & (-idx));
	}
	return value;
}

void update(int idx)
{
	while(idx<=mx)
	{
		sum[idx]+=1;
		idx += (idx & (-idx));
	}
}
int main()
{
	int t,N;
	ll ans;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&N);
		mx=-1;
		for(int i=1;i<=N;i++)
		{
			scanf("%d",&arr[i]);
			if(mx<arr[i])
			mx=arr[i];
		}
		memset(Left,0,sizeof(Left));
		memset(Right,0,sizeof(Right));
		memset(sum,0,sizeof(sum));

		for(int i=1;i<=N;i++)
		{
			Left[i]=Cumulative(arr[i]);//finds the number of smaller number than arr[i] to its Left
			update(arr[i]);
		}
		memset(sum,0,sizeof(sum));
		for(int i=N;i>=1;i--)
		{
			Right[i]=Cumulative(arr[i]);
			update(arr[i]);
			//ans += Left[i]*(N-)
		}
		ans = 0;
		for(int i=N;i>=1;i--)
		{
			ans += Left[i]*(N-i-Right[i]) + Right[i]*(i-1-Left[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

To know something More.

From the above source:

Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions.

Let's take the second example - 2, 3, 8, 6, 1.
BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2:
BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3:
BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8:
BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions
BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions
BIT - 1, 1, 1, 0, 0, 1, 0, 1.

P.S. In the examples I haven't included the compression for clarity.

Sample code implementing the binary indexed tree data structure to find the # of smaller numbers than a number of an array.

#include<iostream>

using namespace std;

int ftree[10000001]={0};

int cum(int idx){
	int result=0;
	while(idx>0){
		result=result+ftree[idx];
		idx=idx-(idx & -idx);
	}

	return result;
}

void update(int idx,int val){
	while(idx<=10000000){
		ftree[idx]=ftree[idx]+val;
		idx=idx+(idx & -idx);
	}
}

int main()
{
	int t;
	cin>>t;
	for(int w=0;w<t;w++){
		int n;
		cin>>n;
		int ele;
		long int count=0;
		for(int i=0;i<n;i++){
			cin>>ele;
			update(ele,1);
			count=count+cum(10000000)-cum(ele);
		}
		cout<<count<<"\n";
		for(int i=1;i<=10000000;i++)
			ftree[i]=0;
	}
	return 0;
}