Utility function to print the original indices of the elements of the array
static void printIndices ( int n , pair a [ ] ) { for ( int i = 0 ; i < n ; i ++ ) System . out . print ( a [ i ] . second + " ▁ " ) ; System . out . println ( ) ; } static class sort implements Comparator < pair > {