// persistent implicit randomized cartesian tree with lazy reverse
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;

mt19937 rng (12345);

struct Node;
typedef Node * PNode;
PNode EMPTY;
struct Node
{
	int value;
	int size;
	bool rev;
	PNode left;
	PNode right;

	Node (int value_)
	{
		value = value_;
		size = 1;
		rev = false;
		left = right = EMPTY;
	}

	Node (PNode other)
	{
		value = other -> value;
		size = other -> size;
		rev = other -> rev;
		left = other -> left;
		right = other -> right;
	}
};

PNode trelax (PNode t)
{
#ifdef DEBUG
	cout << "relax " << t << endl;
#endif
	if (t == EMPTY) return t;
	if (t -> rev)
	{ //  left <-> right, reverse (left), reverse (right)
		t = new Node (t);
		swap (t -> left, t -> right);
		if (t -> left != EMPTY)
			t -> left = new Node (t -> left);
		t -> left -> rev ^= 1;
		if (t -> right != EMPTY)
			t -> right = new Node (t -> right);
		t -> right -> rev ^= 1;
		t -> rev = false;
	}
	return t;
}

void trecalc (PNode t)
{
#ifdef DEBUG
	cout << "recalc " << t << endl;
#endif
	if (t == EMPTY) return;
	t -> size = 1;
	t -> size += t -> left -> size;
	t -> size += t -> right -> size;
}

// t: 100
// t->left: 64
// t: 1
// t->right: 35

// k = 80:
// [0.99] -> [0..79] | [80..99]
pair <PNode, PNode> tsplit (PNode t, int k)
{
#ifdef DEBUG
	cout << "split " << t << " " << k << endl;
#endif
	if (t == EMPTY) return {EMPTY, EMPTY};
	t = trelax (t);
	int leftsize = t -> left -> size + 1;
	if (k - leftsize >= 0)
	{ // 100: 64 + 1 + 35
	  // k = 80 -> 80-64-1
		auto temp = tsplit (t -> right, k - leftsize);
		t = new Node (t);
		t -> right = temp.first;
		trecalc (t);
		return {t, temp.second};
	}
	else
	{ // 100: 64 + 1 + 35
	  // k = 50 -> 50
	  // [0..49]=temp.first, [50..63]=temp.second
	  // [0..49] | [50..99] = [50..63], 64, [65..99]
		auto temp = tsplit (t -> left, k);
		t = new Node (t);
		t -> left = temp.second;
		trecalc (t);
		return {temp.first, t};
	}
}

PNode tmerge (PNode l, PNode r)
{
#ifdef DEBUG
	cout << "merge " << l << " " << r << endl;
#endif
	if (l == EMPTY) return r;
	if (r == EMPTY) return l;
	l = trelax (l);
	r = trelax (r);
	// (100) 100/110       (10) 10/110
	if (rng () % (l -> size + r -> size) < (unsigned) l -> size)
	{ //               l
	  //             /   \ .
	  //    l->left         l->right  r
		l = new Node (l);
		l -> right = tmerge (l -> right, r);
		trecalc (l);
		return l;
	}
	else
	{ //                   r
	  //                 /   \ .
	  //    l  r->left         r->right
		r = new Node (r);
		r -> left = tmerge (l, r -> left);
		trecalc (r);
		return r;
	}
}

PNode tinsert (PNode t, int value, int pos)
{
#ifdef DEBUG
	cout << "insert " << t << " " << value << " " << pos << endl;
#endif
	auto temp = tsplit (t, pos);
	auto cur = new Node (value);
	// temp.first | cur | temp.second
	auto m = tmerge (temp.first, cur);
	return tmerge (m, temp.second);
}

void toutput (PNode t)
{
#ifdef DEBUG
	cout << "output " << t << endl;
	cout << "output " << t << " " <<
	    t -> value << " " << t -> size << endl;
#endif
	if (t == EMPTY) return;
	t = trelax (t);
	toutput (t -> left);
	cout << " " << t -> value;
	toutput (t -> right);
}

void full_output (PNode t)
{
	cout << "[";
	toutput (t);
	cout << "]" << endl;
}

PNode treverse (PNode t, int from, int len)
{ // [0..99]  treverse (t, 40, 50)
  // [0..39]     [40..89]rev  [90..99]
  // temp.first  temp2.first  temp2.second
#ifdef DEBUG
	cout << "reverse " << t << " " << from << " " << len << endl;
#endif
	auto temp = tsplit (t, from);
	auto temp2 = tsplit (temp.second, len);
	temp2.first = new Node (temp2.first);
	temp2.first -> rev ^= 1;
	temp.second = tmerge (temp2.first, temp2.second);
	return tmerge (temp.first, temp.second);
}

PNode root;

int main ()
{
//	srand (12345);
//	rand ();...
	EMPTY = new Node (0x7FFFFFFF);
	EMPTY -> size = 0;
	EMPTY -> left = EMPTY;
	EMPTY -> right = EMPTY;

	ios_base::sync_with_stdio (false);
	cin.tie (0);
	cout.tie (0);

	root = EMPTY;
	int n;
	cin >> n;
	high_resolution_clock::time_point t1 =
	   high_resolution_clock::now ();
	for (int i = 0; i < n; i++)
	{
		int j = i + 1;
		root = tinsert (root, j, root -> size);
	}
	high_resolution_clock::time_point t2 =
	   high_resolution_clock::now ();
	duration <double> time_span =
	  duration_cast <duration <double>> (t2 - t1);

	full_output (root); cout << endl;
	auto root2 = treverse (root, 4, 5);
	full_output (root2); cout << endl;
	auto root3 = treverse (root2, 0, 10);
	full_output (root3); cout << endl;
	full_output (root); cout << endl;
	cout << "It took me " << time_span.count () << " seconds." << endl;
	return 0;
}