// array: push_back in log n, by index in log n
// +cut in log n
// +max on subtree
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <utility>
using namespace std;

int random ()
{
	return (rand () << 15) ^ rand ();
}

struct Node;
typedef Node * PNode;
struct Node
{
	int value;
	int y;
	int size;
	int maxtree;
	PNode left;
	PNode right;

	Node (int value_)
	{
		value = value_;
		y = random ();
		size = 1;
		maxtree = value;
		left = nullptr;
		right = nullptr;
	}

	void recalc ()
	{
		size = 1;
		if (left != nullptr) size += left -> size;
		if (right != nullptr) size += right -> size;
		maxtree = value;
		if (left != nullptr) maxtree = max (maxtree, left -> maxtree);
		if (right != nullptr) maxtree = max (maxtree, right -> maxtree);
	}
};

// 40 = 15 left + 1 root + 24 right
// k = 20
// -> right, k = 20 - 15 - 1 = 4
pair <PNode, PNode> tsplitK (PNode t, int k)
{
	if (t == nullptr) return {nullptr, nullptr};
	int leftSize = (t -> left == nullptr) ? 0 : t -> left -> size;
	if (k - leftSize - 1 >= 0)
	{ // leftSize = 10, k = 80: right, k - leftSize - 1
		auto temp = tsplitK (t -> right, k - leftSize - 1);
		t -> right = temp.first;
		t -> recalc ();
		return {t, temp.second};
	}
	else
	{ // leftSize = 50, k = 25: left, k
		auto temp = tsplitK (t -> left, k);
		t -> left = temp.second;
		t -> recalc ();
		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)
	{
		l -> right = tmerge (l -> right, r);
		l -> recalc ();
		return l;
	}
	else
	{
		r -> left = tmerge (l, r -> left);
		r -> recalc ();
		return r;
	}
}

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

void toutput (PNode t)
{
	toutputrecur (t);
	cout << endl;
}

int kth (PNode & t, int k)
{
	auto temp = tsplitK (t, k);
	auto r = tsplitK (temp.second, 1);
	// temp.first | r.first | r.second
	int res = r.first -> value;
	temp.second = tmerge (r.first, r.second);
	t = tmerge (temp.first, temp.second);
	return res;
}

int main ()
{
/*
	int n = 10;
	PNode root = nullptr;
	for (int i = 1; i <= n; i++)
	{
		int value = (i * 7) % n;
		root = tmerge (root, new Node (value));
		toutput (root);
	}

	for (int i = n - 1; i >= 0; i--)
	{
		cout << kth (root, i) << endl;
	}
*/

	int n = 20;
	PNode root = nullptr;
	for (int i = 1; i <= n; i++)
	{
		int value = (i * 3) % n;
		root = tmerge (root, new Node (value));
	}

	for (int i = 0; i < n; i++)
	{
		cout << kth (root, i) << " ";
	}
	cout << endl;

	int lo = 4;
	int me = 10;
	int hi = 12;
/*
	int lo = 10000;
	int me = 30000;
	int hi = 75000;
*/
	//           half.1            half.2
	// arr: 0 .. lo, lo .. me, me .. hi, hi .. n
	//               ^^^^^^^^  vvvvvvvv
	// arr: 0 .. lo, me .. hi, lo .. me, hi .. n
	{
		auto half = tsplitK (root, me);
		auto one = tsplitK (half.first, lo);
		auto two = tsplitK (half.second, hi - me);
		cout << one.first -> maxtree << " ";
		cout << one.second -> maxtree << " ";
		cout << two.first -> maxtree << " ";
		cout << two.second -> maxtree << "\n";
		auto left = tmerge (one.first, two.first);
		auto right = tmerge (one.second, two.second);
		root = tmerge (left, right);
	}

	for (int i = 0; i < n; i++)
	{
		cout << kth (root, i) << " ";
	}
	cout << endl;

	return 0;
}