// Cartesian tree
// Basic version implementing a set
// tSplit, tMerge: base functions
// tInsert, tRemove, tPrint: set interface
#include <bits/stdc++.h>
using namespace std;

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

	Node (int x_)
	{
		x = x_;
		y = (rand () << 15) ^ rand ();
		left = nullptr;
		right = nullptr;
	}
};

pair <PNode, PNode> tSplit (PNode t, int x)
{ // <x, >=x
	if (t == nullptr) return {nullptr, nullptr};
	if (t->x < x) // 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)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (l->y < r->y)
	{
		r->left = tMerge (l, r->left);
		return r;
	}
	else
	{
		l->right = tMerge (l->right, r);
		return l;
	}
}

PNode tInsert (PNode t, int x)
{
	auto v = new Node (x);
	auto temp = tSplit (t, x);
	return tMerge (temp.first, tMerge (v, temp.second));
}

PNode tRemove (PNode t, int x)
{
	auto temp = tSplit (t, x);
	auto next = tSplit (temp.second, x + 1);
	return tMerge (temp.first, next.second);
}

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

int main ()
{
	PNode root = nullptr;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		root = tInsert (root, i);
//		tPrint (root);
//		cout << endl;
	}
	for (int i = 0; i < n; i++)
	{
		root = tRemove (root, i);
//		tPrint (root);
//		cout << endl;
	}
	return 0;
}