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

// Given an array with N distinct elements, convert the given array to
// a reduced form where all elements are in range from 0 to N-1. The
// order of elements is same, i.e., 0 is placed in place of smallest
// element, 1 is placed for second smallest element, N-1 is placed for
// largest element.

// Note: You don't have to return anything. You just have to change the given array.

class Solution{
public:	
    // Converts arr[0..n-1] to reduced form.
    void convert(int arr[], int n) {
        // code here
        map<int,int> valueToIndexMap;
        for (int i = 0; i < n; i++)
            valueToIndexMap.insert(make_pair(arr[i], i));

        cout << setw(10) << "keys: "; 
        for (auto i: valueToIndexMap)
            cout << setw(3) << i.first << " ";
        cout << endl;
        
        cout << setw(10) << "vals: ";        
        for (auto i: valueToIndexMap)
            cout << setw(3) << i.second << " ";
        cout << endl;

        size_t index = 0;
        // replace each index with reduced index value
        for (auto i: valueToIndexMap)
        {
            arr[i.second] = index++;
        }
    }

    /*
    void convert1(int arr[], int n)
    {
        // push the value and its index as pair into a vector
        vector<pair<int,int>> v;
        for(int i=0; i<n; i++){
            v.push_back({arr[i], i});
        }
        // sort according to the value
        sort(v.begin(), v.end());
	
        int k=0;
        //replace each position with the reduced value
        for(auto it : v){
            arr[it.second] = k++;
        }
    }
    */
};

int main() 
{
    vector<tuple<vector<int>,size_t,vector<int>>> v = {
        { {10,40,20}, 3,
          {0,2,1} },
        { {5, 10, 40, 30, 20}, 5,
          {0,1,4,3,2} },
        { {841,315,752,544,437,646,165,718,773,798,872,329,602,726,687,476,664,631,672,474,724,313}, 22,
          {20,2,17,7,4,10,0,14,18,19,21,3,8,16,13,6,11,9,12,5,15,1} },
    };
    
    for (auto i: v)
    {
        int arr[get<1>(i)];
        cout << setw(10) << "input: ";
        for (size_t j = 0; j < get<1>(i); j++)
        {
            arr[j] = get<0>(i)[j];
            cout << setw(3) << get<0>(i)[j] << " ";
        }
        cout << endl;

        cout << setw(10) << "index: ";
        for (size_t j = 0; j < get<1>(i); j++)
            cout << setw(3) << j << " ";
        cout << endl;        
        
        Solution ob;
        ob.convert(arr, (int)get<1>(i));
        
        cout << setw(10) << "result: ";        
        for (size_t j = 0; j < get<1>(i); j++) {
            cout << setw(3) << arr[j] << " ";
        }
        cout << "\n";
        
        cout << setw(10) << "expected: ";        
        for (size_t j = 0; j < get<2>(i).size(); j++) {
            cout << setw(3) << get<2>(i).at(j) << " ";
        }
        cout << "\n-----------------------\n";
        
    }
    
    return 0;
}