// Randomized implicit Cartesian tree
// Added mass query: sum of values
#include <bits/stdc++.h>
using namespace std;

struct Node;
typedef Node * PNode;
int getSize (PNode);
int64_t getTotal (PNode);
struct Node
{
	int value;
	int size;
	int64_t total;
	PNode left;
	PNode right;

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

	Node (int value_)
	{
		value = value_;
		size = 1;
		total = value;
		left = nullptr;
		right = nullptr;
	}
};

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

int64_t getTotal (PNode t)
{
	return t ? t->total : 0;
}

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 pos, int value)
{
	auto v = new Node (value);
	auto temp = tSplitPos (t, pos);
	return tMerge (temp.first, tMerge (v, temp.second));
}

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

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->value;
	}
	pos -= 1;
	return tFindPos (t->right, pos);
}

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

int main ()
{
	PNode root = nullptr;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		root = tInsert (root, i / 2, i);
		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 = 1; i <= n; i++)
	{
		auto temp = tSplitPos (root, i);
		tPrint (temp.second); cout << ": ";
		cout << getTotal (temp.second) << "; ";
		root = tMerge (temp.second, temp.first);
		tPrint (root); cout << endl;
	}
	return 0;
}