We introduce two ways.

Solution 1 (using std::set).

One way is to use an ordered set type like std::set.
Specifically, we process the events while managing the set of people who have already been called by the teller but have not come, as follows:

• Let called be the set of people who have already been called by the teller but have not come. Initially, called is empty.
• Also, let last be the ID of the person called last time. Initially, let last be \(0\).
• Then, process the events in order. Depending on the event, perform the following operation.
  • If the event is of the first kind, person with ID last + 1 is called next, so increment last by one and insert last to called.
  • If the event is of the second kind, remove x from called.
  • If the event is of the third kind, the answer is the minimum element of called. Print it.

In the procedure above, the operations against called are additions, removals, and retrieval of the minimum element. If you use an array or list to implement called, the worst time complexity will be \(\mathrm{O}(N^2)\) time, which leads to TLE; however, an ordered set type like std::set enables us to perform all of those operations in an \(\mathrm{O}(\log N)\) time each. This way, the problem can be solved in a total of \(\mathrm{O}(Q \log N)\) time over entire queries.

• Sample code (C++, \(\mathrm{O}(Q \log N)\))

#include <iomanip>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;

  set<int> called;
  int last = 0;
  while (Q--) {
    int event;
    cin >> event;
    if (event == 1) {
      called.insert(++last);
    } else if (event == 2) {
      int x;
      cin >> x;
      called.erase(x);
    } else {
      cout << *begin(called) << "\n";
    }
  }
}

Solution 2 (how to solve it in a linear time)

We also introduce a better solution that costs \(\mathrm{O}(N + Q)\) time.

By the constraints of the problem, the events of the third kind occurs with weakly monotonically increasing arguments.

• Proof: we proof by contradiction. Suppose that an event of third kind calls person \(y\), then another afterwards calls person \(x\) \((x < y)\). Then, when person \(y\) is called, person \(x\) has already been called at least once by the teller (because the first call is in the order of their IDs) but has not come, so this is contradiction.

Thus, one can construct a linear-time algorithm that works as follows. We always store in a variable ans the last person called by an event of the third kind. Every time an event of the third kind occurs, we repeatedly increment ans until person ans has not come to the teller, and print resulting ans.
By this operation, the number of times ans is incremented is bounded by \(\min(N, Q)\) times, so the time complexity is \(\mathrm{O}(N+ Q)\).

• Sample code (C++, \(\mathrm{O}(N + Q)\))

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  vector<int> gone(N + 1);
  int ans = 1;
  while (Q--) {
    int event;
    cin >> event;
    if (event == 1) {
      // do nothing
    } else if (event == 2) {
      int x;
      cin >> x;
      gone[x] = 1;
    } else {
      while (gone[ans]) ans++;
      cout << ans << "\n";
    }
  }
}