#include "majority.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

namespace {
using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

int Q;
vector<D_t> X{D_t(-1)};
vector<int> mate{-1};
set<int> rems;

bool answer() {
  if (rems.size()) {
    submit(X[*rems.begin()]);
    return true;
  } else {
    return false;
  }
}
}  // namespace

bool insert(const D_t &x) {
  ++Q;
  X.push_back(x);
  mate.push_back(-1);
  if (rems.size()) {
    const int r = *rems.begin();
    if (X[r] == X[Q]) {
      rems.insert(Q);
    } else {
      mate[r] = Q;
      mate[Q] = r;
      rems.erase(rems.begin());
    }
  } else {
    rems.insert(Q);
  }
  return answer();
}

bool erase(int id) {
  if (~mate[id]) {
    const int m = mate[id];
    mate[id] = mate[m] = -1;
    if (rems.size()) {
      const int r = *rems.begin();
      if (X[r] == X[m]) {
        rems.insert(m);
      } else {
        mate[r] = m;
        mate[m] = r;
        rems.erase(rems.begin());
      }
    } else {
      rems.insert(m);
    }
  } else {
    rems.erase(id);
  }
  return answer();
}