#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

using namespace std;

void CountInversions(int *vals, int numVals, long long *counter) {
   int baseIdx, cmpIdx;
   long long subCount;      

   for (baseIdx = 0; baseIdx < numVals; baseIdx++)
      for (cmpIdx = baseIdx + 1; cmpIdx < numVals; cmpIdx++)
         if (vals[baseIdx] > vals[cmpIdx]) 
            (*counter)++;
}

// Count number of inversions in an array of size specified by commandline 
// argument, and filled with inverse-order values.  Spread the work among
// a number of threads also specified in commandline arguments.
int main(int argc, char* argv[]) {
   int idx, numVals;
   long long numInvs = 0;
   int *vals;

   if (argc != 2)
      cout << "Usage: InvCounter <numVals>" << endl;
   else {
      numVals = atoi(argv[1]);
   }

   vals = (int *)calloc(sizeof(int), numVals);

   // Fill array in inverted order to maximize number of inversions
   for (idx = 0; idx < numVals; idx++)
      vals[idx] = numVals - idx;

   CountInversions(vals, numVals, &numInvs);

   cout << "Number of inversions: " << numInvs << endl;
   return 0;
}