#include <bits/stdc++.h>
using namespace std;

/*
  An array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].
  
  Write a function:
  
        class Solution { public int solution(int[] A); }

  that computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.

  For example, in the following array:

  A[0] = -1 A[1] = 6 A[2] = 3
  A[3] =  4 A[4] = 7 A[5] = 4
  
  there are four inversions:

      (1,2)  (1,3)  (1,5)  (4,5)
      
  so the function should return 4.

  Write an efficient algorithm for the following assumptions:

  N is an integer within the range [0..100,000];

  each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

  Inversion Count for an array indicates – how far (or close) the array
  is from being sorted. If the array is already sorted, then the
  inversion count is 0, but if the array is sorted in reverse order, the
  inversion count is the maximum.

  Use Merge sort with modification that every time an unsorted pair is found increment count by one and return count at the end.
*/

ostream& operator<<(ostream& os, const pair<int,int>& p)
{
    return os << "(" << p.first << "," << p.second << ")";
}

void printVPair(vector<pair<int,int>>& v) { for (auto i: v) { cout << i << " "; } cout << endl; }

class Solution
{
public:
    
    int solution(vector<int>& A)
    {
        int result = 0;
        vector<pair<int,int>> v;

        // brute force
        for (size_t i = 0; i < A.size() - 1; i++)
        {
            for (size_t j = i + 1; j < A.size(); j++)
            {
                if (A.at(i) > A.at(j))
                {                    
                    result += 1;
                    v.push_back({i,j});
                }
            }
        }

        cout << "solution: "; printVPair(v); cout << endl;
        
        return result;
    }
};
    
int main(void)
{
    vector<tuple<vector<int>,vector<pair<int,int>>>> testCases = {
// indices:  0 1 2 3 4 5    inversions
         { {-1,6,3,4,7,4}, {{1,2},{1,3},{1,5},{4,5}} },
         { {5,4,3,2,1}, {{5,4},{5,3},{5,2},{5,1},{4,3},{4,2},{4,1},{3,2},{3,1},{2,1}} },
    };

    for (auto tc: testCases)
    {
        Solution s;
        vector<int>& input = get<0>(tc);
        vector<pair<int,int>>& expected = get<1>(tc);
        int result = s.solution(input);

        auto printV = [](vector<int>& v)
        { for (auto i: v) { cout << i << " "; } cout << endl; };
        
        int width = 10;
        cout << setw(width) << "input: "; printV(input);
        cout << setw(width) << "result: " << result << endl;
        cout << setw(width) << "expected: " << expected.size() << " inversions: "; printVPair(expected);
        cout << ((size_t)result == expected.size() ? "\033[32mpassed\033[0m" : "\033[31mfailed\033[0m") << endl;
        cout << "----------------------------\n";
    }
}