/**
 * // This is the interface that allows for creating list of lists.
 * // You should not implement it, or speculate about its implementation
 * class ListOfList {
 *   public:
 *     // Return true if this ListOfList holds a single integer, rather than a list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this ListOfList holds, if it holds a single integer
 *     // The result is undefined if this ListOfList holds a list
 *     int getInteger() const;
 *
 *     // Return the list that this ListOfList holds, if it holds a list
 *     // The result is undefined if this ListOfList holds a single integer
 *     const vector<ListOfList> &getList() const;
 * };
 */

class ListIterator {
public:
    ListIterator(vector<ListOfList> &listOfList) {
    }
    
    int next() {
    }
    
    bool hasNext() {
    }
};


/**
 * Your ListIterator object will be instantiated and called as such:
 * ListIterator i(listOfList);
 * while (i.hasNext()) cout << i.next();
 */


 Example (1)
Input: listOfList = [1,[4,[6]]]
Output: [1,4,6]

 Example (2)
Input: [1, [2, 3, [4, 5, []], 6], 7]
Output: [1, 2, 3, 4, 5, 6, 7]

class ListIterator {
    vector<ListOfList> ll;
    vector<ListOfList>::iterator it = ll.begin();
public:
    //Input: [1, [2, 3, [4, 5, []], 6], 7]
    ListIterator(vector<ListOfList> &listOfList) {
        ll = listOfList;
    }
    
    int next() {
        if (hasNext()){
            for (auto i=it.begin(); i !=it.end(); ++i){
                //Check the single ll
                list<int>::iterator single& = *i;
                for (auto j=single.begin(); j!=single.end(); ++j){
                    return *j;
                }
            }
            //it = i;
        }
        return 0;
    }
    
    bool hasNext() {
        if it != ll.end()
            return true;
        return false
    }
};

struct node {
  int a;
  struct node* another_list;
  struct node* next;
};

                                4->5
             1 -> 2 -> 3,/\->6

Example-1
        a          b        c         d         e
Input: [8000,1], [5000,3], [8000,0], [6000,2], [6000,0]
    city          a       b     c     d       e
    population:   8000    5000  8000  6000   6000
    //There should be:
      1 cities to left of city=a, whose population >= 8000.
      3 cities to left of city=b, whose population >= 5000
      0 city to left of city=c, whose population >= 8000
      2 city to left of city=d, whose population >= 6000      
      0 cities to left of city=e, whose population >= 6000

Output: [6000,0] [8000,0] [6000, 2] [5000, 3] [8000, 1]

Example-2
        a         b       c         d
Input: [800,0], [700,0], [300,1], [600,2]
  0 cities to left of city=a whose population >= 800
  0 cities to left of city=b whose population >= 700
  1 city to left of city=c whose population   >= 300
  2 cities to left of city=d whose population >= 600

Output: [700,0][300,1][800,0][600,2]

input = [8000,1], [5000,3], [8000,0], [6000,2], [6000,0]

1a. sorted in desc order by population:
        [8000,1] [8000,0] [6000,2] [6000,0] [5000,3]
        
1b. if population is same, sort by second element
        [8000,0] [8000,1] [6000,0] [6000,2] [5000,3]

    [8000,0] [8000,1] [6000,0] [6000,2] [5000,3]
    
    Index of:
      [6000,0] should be 0.   [6000,0] [8000,0] [8000,1] [6000,2] [5000,3]
      [6000,2] should be 2.   [6000,0] [8000,0] [6000,2] [8000,1] [5000,3]
      [5000,3] should be 3.   [6000,0] [8000,0] [6000,2] [5000,3] [8000,1]
      
Ans: [6000,0] [8000,0] [6000,2] [5000,3] [8000,1]

#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
using mpair = pair<int,int>;

bool comparator(pair<int,int> p1, pair<int,int> p2){
    if(p1.first == p2.first)
      return p1.second < p2.second;

    return p1.first > p2.first;
}

//i = {8000,1}, {5000,3}, {8000,0}, {6000,2}, {6000,0}
vector<mpair> fun(vector<mpair> input) {
    vector<mpair> o;

    sort(input.begin(), input.end(), comparator);

    //After sort
    //i = {8000,0}, {8000,1}, {6000,0}, {6000,2}, {5000,3}

    for (int i=0; i<input.size(); ++i)
        o.insert(o.begin()+input[i].second, input[i]);

    return o;
}

int main(){
    vector<pair<int,int>> i = {{8000,1}, {5000,3}, {8000,0}, {6000,2}, {6000,0}};
    vector<mpair> o = fun(i);
    for (auto j:o){
        cout << j.first <<"," << j.second;
        cout <<"\n";
    }
}
# ./a.out
6000,0
8000,0
6000,2
5000,3
8000,1