struct Seg
{
	int l, r;

	Seg () {}

	Seg (int _l, int _r)
	{
		l = _l, r = _r;
	}
};

struct Decomposition
{
	int n;
	vector < Seg > b;
	vector < int > a;

	Decomposition () {}

	Decomposition (int _n, const vector < int > & _a)
	{
		n = _n, a = _a;
		b.push_back(Seg(1, n));
	}
	void rebuild()
	{
		vector < int >_a(1);
		int cnt = 0;
		for (auto &it : b)
		{
			for (int i = it.l; i <= it.r; i++)
			{
				_a.push_back(a[i]);
				cnt++;
			}
		}
		n = cnt;
		a = _a;
		b.clear();
		b.push_back(Seg(1, n));
		_a.clear();
	}
	void print()
	{
		for (auto &it : b)
			cerr << it.l << ' ' << it.r << endl;
		for (int i = 0; i < (int)a.size(); i++)
			cerr << a[i] << ' ';
		cerr << endl;
	}
	int split(int l)
	{
		int cnt = b[0].r - b[0].l + 1, pos = 0;
		while(cnt < l)
		{
 			pos++;
 			cnt += b[pos].r - b[pos].l + 1;
		}
		if (l != cnt)
		{
			int r = b[pos].r;
			int len = b[pos].r - b[pos].l + 1 - cnt + l;
			b[pos].r = b[pos].l + len - 1;
			b.insert(b.begin() + pos + 1, Seg(b[pos].l + len, r));
		}
		return pos;
	}
	void add(int x, int y)
	{
		int pos = split(x);
		a.push_back(y);
		n++;
		b.insert(b.begin() + pos + 1, Seg(n, n));

		if ((int)b.size() > MAGIC)
			rebuild();
	}
	void del(int x)
	{
		split(x);
		int pos = split(x - 1);
		b.erase(b.begin() + pos + 1);
		if ((int)b.size() > MAGIC)
			rebuild();
	}
};