// Cartesian tree
// Ordered set version
// added tSplitSize and tFindSize
// #define _GLIBCXX_DEBUG 1
#include <bits/stdc++.h>
using namespace std;

struct Node
{
	int x;
	int y;
	int size;
	Node* left;
	Node* right;
	
	void recalc ()
	{
		size = 1;
		if (left != nullptr) size += left->size;
		if (right != nullptr) size += right->size;
	}
	
	Node (int x_) : x (x_), y ((rand() << 15) | rand()),
	                size (1), left (nullptr), right (nullptr)
	{}
};

pair <Node*, Node*> tSplit (Node* t, int x)
{
	if (t == nullptr) return {nullptr, nullptr};
	if (t->x >= x)
	{
		auto temp = tSplit (t->left, x);
		t->left = temp.second;
		t->recalc();
		return {temp.first, t};
	}
	else
	{
		auto temp = tSplit (t->right, x);
		t->right = temp.first;
		t->recalc();
		return {t, temp.second};
	}
}

pair <Node*, Node*> tSplitSize (Node* t, int k)
{ // [0..k) | [k..oo)
	if (t == nullptr) return {nullptr, nullptr};
	auto tLeftSize = t->left ? t->left->size : 0;
	if (k <= tLeftSize) // k < (tLeftSize + 1)
	{
		auto temp = tSplitSize (t->left, k);
		t->left = temp.second;
		t->recalc();
		return {temp.first, t};
	}
	else
	{
		auto temp = tSplitSize (t->right, k - (tLeftSize + 1));
		t->right = temp.first;
		t->recalc();
		return {t, temp.second};
	}
}

Node* tMerge (Node* l, Node* r)
{
	if (l == nullptr) return r;
	if (r == nullptr) return l;
	if (l->y > r->y)
	{
		l->right = tMerge (l->right, r);
		l->recalc();
		return l;
	}
	else
	{
		r->left = tMerge (l, r->left);
		r->recalc();
		return r;
	}
}

Node * tInsert (Node* t, int x)
{
	pair <Node*, Node*> temp = tSplit (t, x);
	Node* v = new Node (x);
	Node* half = tMerge (temp.first, v);
	return tMerge (half, temp.second);
}

Node * tRemove (Node* t, int x)
{
	pair <Node*, Node*> one = tSplit (t, x);
	pair <Node*, Node*> two = tSplit (one.second, x + 1);
	// todo: delete
	return tMerge (one.first, two.second);
}

bool tFind (Node* t, int 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);
}

int tFindSize (Node* t, int k)
{
	if (t == nullptr) assert (false);
	auto tLeftSize = t->left ? t->left->size : 0;
	if (k < tLeftSize)
		return tFindSize (t->left, k);
	k -= tLeftSize;
	if (k == 0) return t->x;
	k -= 1;
	return tFindSize (t->right, k);
}

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

void tPrint (Node* t)
{
	tPrintRecur (t);
	cout << endl;
}

int main ()
{
	int limit;
	cin >> limit;
	srand(time(nullptr));
	Node* root = nullptr;
//	for (int i = 1; i <= limit; i += 2)
	for (auto i : vector <int> ({3, 7, 18, 2, 4, 7, 8}))
	{
		root = tInsert (root, i);
//		tPrint (root);
	}
//	tPrint (root);
	for (int i = 0; i < 7; i++)
	{
		cout << i << ": " << tFindSize (root, i) << endl;
//		tPrint (root);
	}
	tPrint (root);
	for (int i = 0; i <= 7; i++)
	{
		auto temp = tSplitSize (root, i);
//		cout << i << ": " << tFindSize (root, i) << " ";
		tPrintRecur (temp.first);
		cout << " + ";
		tPrint (temp.second);
		root = tMerge (temp.first, temp.second);
//		tPrint (temp.second);
	}
/*
	for (int i = 1; i <= limit; i++)
	{
		root = tInsert (root, 0);
	}
	int j = limit + 3;
	cout << j << ": " << tFindSize (root, j) << endl;
*/
}