/*
  Problem 1656. Design an Ordered Stream
  
  There is a stream of n (idKey, value) pairs arriving in an arbitrary
  order, where idKey is an integer between 1 and n and value is a
  string. No two pairs have the same id.
  

  Design a stream that returns the values in increasing order of their
  IDs by returning a chunk (list) of values after each insertion. The
  concatenation of all the chunks should result in a list of the
  sorted values.
  

  Implement the OrderedStream class:

  OrderedStream(int n) Constructs the stream to take n values.
  
  String[] insert(int idKey, String value) Inserts the pair (idKey,
  value) into the stream, then returns the largest possible chunk of
  currently inserted values that appear next in the order.
*/

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

class OrderedStream {
public:
    vector<string> stream;
    size_t ptr = 0;
    
    OrderedStream(int n) {
        stream.resize(n);
    }

    // idKeys start at 1, not zero
    vector<string> insert(int idKey, string value) {
        stream.at(idKey-1) = value;
        vector<string> result;
        while (ptr < stream.size() && !stream.at(ptr).empty())
            result.push_back(stream.at(ptr++));
        return result;
    }
};

int main(void)
{
    vector<tuple<int,vector<pair<int,string>>>> testCases {
        { 5, {{3,"ccccc"},{1,"aaaaa"},{2,"bbbbb"},{5,"eeeee"},{4,"ddddd"}} },
    };

    cout << "Start" << endl;
    cout << get<0>(testCases.at(0)) << endl;    
    vector<pair<int,string>>& v = get<1>(testCases.at(0));
    for (auto i: v)
    {
        cout << i.first << " " << i.second << endl;
    }
    
    for (auto tc: testCases)
    {
        OrderedStream os(get<0>(tc));
        cout << os.stream.size() << endl;
        vector<pair<int,string>>& v = get<1>(tc);
        for (auto i: v)
        {
            vector<string> res = os.insert(i.first, i.second);
            cout << "result: ";
            for (auto i: res)
                cout << i << " ";
            cout << endl;
        }
    }

    return 0;    
}