//#include<bits/stdc++.h>
//#include "majority.h" 
//#define L(i, j, k) for(int i = (j); i <= (k); i++)
//#define R(i, j, k) for(int i = (j); i >= (k); i--)
//#define ll long long
//#define ull unsigned long long 
//#define sz(a) ((int) a.size())
//#define vi vector<int>
//#define me(a, x) memset(a, x, sizeof(a))
//#define i128 __int128 
//using namespace std;
//const int N = 1e6 + 7;
//
//#define A D_t
//
//struct inter {
//	int l, r;
//	A w;
//	set < int > st;
//} it[N];
//set < int > con[N];
//
//inline int find(int x) {
//	return f[x] == x ? x : f[x] = find(f[x]);
//}
//
//int mg(int a, int b) {
//	int len = min(it[a].r, it[b].r) - max(it[a].l, it[b].l) + 1;
//	if(len <= 0) assert(false);
//	int l = min(it[a].l, it[b].l) - len / 2 - 1, r = max(it[a].r, it[b].r) + len / 2 + 1;
//	if(sz(it[a].st) < sz(it[b].st)) {
//		swap(a, b);
//	}
//	int ql = it[a].l, qr = it[a].r;
//	
//	it[a].l = l, it[b].r = r;
//	for(auto p : it[b].st) 
//		it[a].st.insert(p);
//	
//	L(j, st[b].l, st[b].r) st[j].erase(b);
//	L(j, it[a].l, ql - 1) st[j].insert(a);
//	L(j, qr + 1, it[a].r) st[j].insert(a);
//	
//	return a;
//}
//
//int cur, tp, cnts;
//A f[N];
//bool ok[N];
//
//inline int lst(int x) {
//	while(x && !ok[x]) 
//		--x;
//	return x;
//}
//inline int nxt(int x) {
//	while(x <= cur && !ok[x]) 
//		++x;
//	return x;
//}
//
//int fib = 1;
//bool print() {
//	if(!cnts) 
//		return false;
//	while(ok[fib]) 
//		++fib;
//	for(auto u : con[fib]) 
//		if(sz(it[u].st) > cnts / 2) 
//			return submit(it[u].w), true;
//	return false;
//}
//
//bool insert(const D_t& x) {
//	++cur, ++cnts;
//	f[cur] = x, ok[cur] = true;
//	it[cur].l = cur - 1, it[cur].r = cur + 1, it[cur].w = ;
//	
//	
//	for(auto u : con[cur - 1]) 
//		 
//		 
//		
//		
//	submit(A.w);
//	
//	return print();
//}
//
//bool erase(int id) {
//	--cnts;
//	ok[id] = false;
//	
//	return print();
//}

#include<bits/stdc++.h>
#include "majority.h" 
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define ull unsigned long long 
#define sz(a) ((int) a.size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
#define i128 __int128 
using namespace std;
const int N = 1e6 + 7;

#define A D_t

int cnt[N];
int cnts, up[N];
int mx;

set < pair < int, int > > st;

int lim, cur, f[N];

bool print() {
	if(!lim) return false;
	if((--st.end()) -> first > lim / 2) 
		return submit(D_t((--st.end()) -> second)), true;
	return false;
}

bool insert(const D_t& x) {
	++lim; 
	
	int l = 0, r = 1e5, ns = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(x <= D_t(mid)) ns = mid, r = mid - 1;
		else l = mid + 1;
	}
//	cerr << "ns = " << ns << endl;
	
	f[++cur] = ns;
	
	if(cnt[ns]) st.erase({cnt[ns], ns});
	cnt[ns] += 1;
	st.insert({cnt[ns], ns});
	
	return print();
}

bool erase(int id) {
	--lim;
	
	st.erase({cnt[f[id]], f[id]});
	cnt[f[id]] -= 1;
	if(cnt[f[id]]) st.insert({cnt[f[id]], f[id]});
	
	return print();
}