// Randomized Cartesian tree
// Removed y
// Use sizes for probabilistic balancing
// Note: just merging into random with probability 1/2 is too slow
#include <bits/stdc++.h>
using namespace std;

struct Node;
typedef Node * PNode;
int getSize (PNode);
struct Node
{
	int x;
	int size;
	PNode left;
	PNode right;

	void recalc ()
	{
		size = 1 + getSize (left) + getSize (right);
	}

	Node (int x_)
	{
		x = x_;
		size = 1;
		left = nullptr;
		right = nullptr;
	}
};

int getSize (PNode t)
{
	return t ? t->size : 0;
}

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;
		t->recalc ();
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplit (t->left, x);
		t->left = temp.second;
		t->recalc ();
		return {temp.first, t};
	}
}

pair <PNode, PNode> tSplitPos (PNode t, int pos)
{ // [0..pos) + [pos..oo)
	if (t == nullptr) return {nullptr, nullptr};
	if (pos >= getSize (t->left) + 1)
	{
		auto temp = tSplitPos (t->right, pos - (getSize(t->left) + 1));
		t->right = temp.first;
		t->recalc ();
		return {t, temp.second};
	}
	else
	{
		auto temp = tSplitPos (t->left, pos);
		t->left = temp.second;
		t->recalc ();
		return {temp.first, t};
	}
}

int random (int limit)
{ // TODO: uniform_int_distribution <int>
	unsigned temp = (rand() << 15) ^ rand();
	return temp % limit;
}

PNode tMerge (PNode l, PNode r)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (random (l->size + r->size) < l->size)
	{
		l->right = tMerge (l->right, r);
		l->recalc ();
		return l;
	}
	else
	{
		r->left = tMerge (l, r->left);
		r->recalc ();
		return r;
	}
}

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);
}

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

int tFindPos (PNode t, int pos)
{
	if (t == nullptr) assert (false);
	if (pos < getSize (t->left))
	{
		return tFindPos (t->left, pos);
	}
	pos -= getSize (t->left);
	if (pos == 0)
	{
		return t->x;
	}
	pos -= 1;
	return tFindPos (t->right, pos);
}

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

int main ()
{
	PNode root = nullptr;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		root = tInsert (root, i * 3 + 8);
		if (i < 30) {tPrint (root); cout << endl;}
	}
	for (int i = 0; i < n; i++)
	{
		int x = tFindPos (root, i);
//		if (i < 30) cout << x << endl;
	}
/*
	for (int i = 0; i <= n; i++)
	{
		auto temp = tSplitPos (root, i);
		if (i < 30 || n - i <= 30) cout << getSize (temp.first) << " " <<
		    getSize (temp.second) << endl;
		root = tMerge (temp.first, temp.second);
	}
*/
	return 0;
}