// Cartesian tree: tSplit+tMerge, tInsert+tRemove, debug output
#include <bits/stdc++.h>
using namespace std;

using Num = int;

mt19937 rndBits (123456);
#ifdef DEBUG
uniform_int_distribution <int> gen (0, 100);
#else
uniform_int_distribution <int> gen (0, 1000000000);
#endif

struct Node;
typedef Node * PNode;
struct Node
{
	Num x;
	int y;
	PNode left;
	PNode right;

	Node (Num x_)
	{
		x = x_;
		y = gen (rndBits);
		left = nullptr;
		right = nullptr;
	}
};

pair <PNode, PNode> tSplit (PNode t, Num x)
{ // res.first: all x < our x;  res.second: all x >= our x
	if (t == nullptr) return {nullptr, nullptr};
	if (t -> x < x)
	{
		auto temp = tSplit (t -> right, x);
		t -> right = temp.first;
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplit (t -> left, x);
		t -> left = temp.second;
		return {temp.first, t};
	}
}

PNode tMerge (PNode l, PNode r)
{ // all x of l < all x < r  --->>>  one new tree
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (l -> y > r -> y)
	{
		l -> right = tMerge (l -> right, r);
		return l;
	}
	else
	{
		r -> left = tMerge (l, r -> left);
		return r;
	}
}

PNode tInsert (PNode t, Num x)
{ // all temp.first x  <  all v x  <=  all temp.second x
	auto temp = tSplit (t, x);
	auto v = new Node (x);
	auto half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

void recurDelete (PNode t)
{
	if (t == nullptr) return;
	recurDelete (t -> left);
	recurDelete (t -> right);
	delete t;
}

PNode tRemove (PNode t, Num x)
{ // all one.first x  <  all two.first x  <  all two.second x
	auto one = tSplit (t, x);
	auto two = tSplit (one.second, x + 1); // depends on Num
	recurDelete (two.first); // can omit this
	return tMerge (one.first, two.second);
}

bool tFind (PNode t, Num x)
{
	if (t == nullptr) return false;
	if (x == t -> x) return true;
	if (x < t -> x) return tFind (t -> left, x);
	return tFind (t -> right, x);
}

void tOutput (PNode t)
{
	if (t == nullptr) return;
	cout << "(";
	tOutput (t -> left);
	cout << t -> x << "|" << t -> y;
	tOutput (t -> right);
	cout << ")";
}

void tOutputAll (PNode t)
{
#ifdef DEBUG
	tOutput (t);
	cout << endl;
#else
	assert (t == NULL || t != NULL);
#endif
}

int main ()
{
	PNode root = nullptr;
	int const limit = 1000000;
/*
	for (int i = 0; i < limit; i++)
	{
		root = tInsert (root, 0);
		tOutputAll (root);
	}
*/
	for (int i = 0; i < limit; i++)
	{
		root = tInsert (root, i);
		tOutputAll (root);
	}
	for (int i = 1; i < limit; i += 2)
	{
		root = tRemove (root, i);
		tOutputAll (root);
	}
	for (int i = 0; i < limit; i++)
	{
		cout << tFind (root, i) << endl;
	}
	return 0;
}