#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")

template <class T> struct SplaySimple {
  SplaySimple *p, *l, *r;
  T t;
  SplaySimple() : p(nullptr), l(nullptr), r(nullptr), t() {}
  void rotate() {
    if (p->l == this) { if (r) { r->p = p; } p->l = r; r = p; }
    else              { if (l) { l->p = p; } p->r = l; l = p; }
    SplaySimple *pp = p->p;
    if (pp) ((pp->l == p) ? pp->l : pp->r) = this;
    p->p = this; p = pp;
  }
  SplaySimple *splay() {
    for (; p; rotate()) if (p->p) ((p->l == this) == (p->p->l == p)) ? p->rotate() : rotate();
    return this;
  }
  SplaySimple *linkL(SplaySimple *a) { assert(!l); l = a; if (l) { l->p = this; } return this; }
  SplaySimple *linkR(SplaySimple *a) { assert(!r); r = a; if (r) { r->p = this; } return this; }
  SplaySimple *cutL() { if (l) { l->p = nullptr; l = nullptr; } return this; }
  SplaySimple *cutR() { if (r) { r->p = nullptr; r = nullptr; } return this; }
  SplaySimple *leftmost() {
    SplaySimple *a = this;
    for (; a->l; a = a->l) {}
    return a->splay();
  }
  SplaySimple *rightmost() {
    SplaySimple *a = this;
    for (; a->r; a = a->r) {}
    return a->splay();
  }
  template <class F> void dfs(F f) {
    if (l) l->dfs(f);
    f(this);
    if (r) r->dfs(f);
  }
  friend SplaySimple *concat(SplaySimple *a, SplaySimple *b) {
    if (!a) return b;
    if (!b) return a;
    return a->splay()->rightmost()->linkR(b->splay());
  }
};

////////////////////////////////////////////////////////////////////////////////

struct Node;
using Tree = SplaySimple<Node>;
struct Node {
  Tree *l1, *r1;
  D_t val;
  Node() : l1(nullptr), r1(nullptr), val(-1) {}
};

int Q = 0;
Tree nodes[100'010];

// path: pointer to the rightmost node on the path
// rems: pointer to the root of the tree for the remaining nodes
Tree *path = nullptr, *rems = nullptr;

bool answer() {
/*
vector<Tree *>as;
for(Tree*a=path;a;a=a->t.l1)as.push_back(a);
reverse(as.begin(),as.end());
cerr<<"path = ";for(Tree*a:as)cerr<<make_pair(a-nodes,a->t.val.get_value())<<" ";cerr<<endl;
cerr<<"rems = ";if(rems)rems->dfs([&](Tree*a)->void{cerr<<make_pair(a-nodes,a->t.val.get_value())<<" ";});cerr<<endl;
for(int q=1;q<=Q;++q)if(!nodes[q].p&&(nodes[q].l||nodes[q].r)){
 cerr<<"  chain ";nodes[q].dfs([&](Tree*a)->void{cerr<<make_pair(a-nodes,a->t.val.get_value())<<" ";});cerr<<endl;
}
for(int q=1;q<=Q;++q)if(nodes[q].t.l1)assert(nodes[q].t.l1->t.r1==&nodes[q]);
for(int q=1;q<=Q;++q)if(nodes[q].t.r1)assert(nodes[q].t.r1->t.l1==&nodes[q]);
for(int q=1;q<=Q;++q)if(nodes[q].p)assert(nodes[q].p->l==&nodes[q]||nodes[q].p->r==&nodes[q]);
for(int q=1;q<=Q;++q)if(nodes[q].l)assert(nodes[q].l->p==&nodes[q]);
for(int q=1;q<=Q;++q)if(nodes[q].r)assert(nodes[q].r->p==&nodes[q]);
//*/
  if (path) {
    if (!path->splay()->leftmost()->t.l1) {
      submit(path->t.val);
      return true;
    } else {
      assert(!rems);
      return false;
    }
  } else {
    assert(!rems);
    return false;
  }
}

void insertBetw(Tree *l, Tree *r, Tree *a) {
  if (l) l->t.r1 = a;
  a->t.l1 = l;
  a->t.r1 = r;
  if (r) r->t.l1 = a;
}
void checkL2(Tree *a, bool ask) {
  if (!ask || (a->t.l1 && a->t.l1->t.l1 && a->t.l1->t.l1->t.val == a->t.val)) {
    concat(a->t.l1->t.l1, a);
  }
}
void checkR2(Tree *a, bool ask) {
  if (!ask || (a->t.r1 && a->t.r1->t.r1 && a->t.val == a->t.r1->t.r1->t.val)) {
    concat(a, a->t.r1->t.r1);
  }
}
}  // namespace

bool insert(const D_t &val) {
  Tree *a = &nodes[++Q];
  a->t.val = val;
// cerr<<COLOR("33")<<"insert "<<make_pair(a-nodes,a->t.val.get_value())<<COLOR()<<endl;
  if (path) {
    if (path->t.val == a->t.val) {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
      Tree *b = path->splay()->leftmost();
      if (b->t.l1) {
        insertBetw(b->t.l1->t.l1, b->t.l1, a);
        a->t.r1->splay()->cutL();
        checkL2(a, true);
        checkR2(a, false);
      } else {
        rems = concat(rems, a);
      }
    } else {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
      path->t.r1 = a;
      a->t.l1 = path;
      checkL2(a, true);
      path = a;
      if (rems) {
        Tree *b = rems;
        {
          Tree *l = b->l, *r = b->r;
          b->cutL()->cutR();
          rems = concat(l, r);
        }
        path->t.r1 = b;
        b->t.l1 = path;
        concat(path->t.l1, b);
        path = b;
      }
    }
  } else {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
    path = a;
  }
  return answer();
}

bool erase(int id) {
  Tree *a = &nodes[id];
// cerr<<COLOR("33")<<"erase "<<make_pair(a-nodes,a->t.val.get_value())<<COLOR()<<endl;
  if (!a->t.l1 && !a->t.r1 && a != path) {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
    a->splay();
    Tree *l = a->l, *r = a->r;
    a->cutL()->cutR();
    rems = concat(l, r);
  } else {
    if (rems && !a->splay()->leftmost()->t.l1) {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
      Tree *b = rems;
      {
        Tree *l = b->l, *r = b->r;
        b->cutL()->cutR();
        rems = concat(l, r);
      }
      if (a->t.l1) a->t.l1->t.r1 = b;
      if (a->t.r1) a->t.r1->t.l1 = b;
      b->t.l1 = a->t.l1;
      b->t.r1 = a->t.r1;
      {
        a->splay();
        Tree *l = a->l, *r = a->r;
        a->cutL()->cutR();
        b->linkL(l)->linkR(r);
      }
      if (!b->t.r1) path = b;
    } else {
      Tree *b = a->t.l1;
      Tree *c = a->t.r1;
      if (b && c && b->splay()->r) {
        Tree *d = b->splay()->leftmost();
        Tree *e = c->splay()->rightmost();
        if (b->t.l1) b->t.l1->t.r1 = c;
        c->t.l1 = b->t.l1;
        {
          a->splay();
          Tree *l = a->l, *r = a->r;
          a->cutL()->cutR();
          concat(l, r);
        }
        {
          b->splay();
          Tree *l = b->l, *r = b->r;
          b->cutL()->cutR();
          concat(l, r);
        }
        {
          Tree *f = c->t.r1;
          if (f && !f->splay()->l) {
            checkL2(f, true);
          }
        }
        if (d->t.l1) {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
          insertBetw(d->t.l1->t.l1, d->t.l1, b);
          b->t.r1->splay()->cutL();
          checkL2(b, true);
          checkR2(b, false);
        } else if (e->t.r1) {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
          insertBetw(e->t.r1, e->t.r1->t.r1, b);
          b->t.l1->splay()->cutR();
          checkL2(b, false);
          checkR2(b, true);
          if (!b->t.r1) path = b;
        } else {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
          rems = concat(rems, b);
          b->t.l1 = b->t.r1 = nullptr;
        }
      } else {
// cerr<<COLOR("32")<<"Case "<<__LINE__<<COLOR()<<endl;
        a->splay()->cutL()->cutR();
        if (b) b->t.r1 = c;
        if (c) c->t.l1 = b;
        if (b && c) {
          if (b->t.l1 && b->t.l1->t.val == c->t.val) concat(b->t.l1, c);
          if (c->t.r1 && b->t.val == c->t.r1->t.val) concat(b, c->t.r1);
        }
        if (!c) path = b;
      }
    }
  }
  a->t.l1 = a->t.r1 = nullptr;
  return answer();
}