Bad Treap

A treap, also known as a Cartesian tree, is a data structure that stores a set of keys in a binary search tree.

Each node of this tree is characterized by a pair (x, y).

The x values of the nodes are the stored keys. They obey the binary search tree rule: all x values in the left subtree of a node are smaller than its x value, and all x values in the right subtree are larger.

The y values of the nodes obey the heap rule: the y value of a node is less than or equal to the y value of its parent.

The y value for each created node is usually chosen randomly according to some distribution. This gives good average time complexity for many operations.

The name is a portmanteau of two words: TRee + hEAP = TREAP.

A treap with 7 nodes; its height is 4	A treap for the sample test

Benjamin decided that nondeterminism in choosing y is bad, because the execution time changes from one run to another. He calculates y for each node deterministically from its x, using the rule $y = \sin(x)$. He is especially glad that distinct integer x values always have distinct y values.

Barbara knows that a nondeterministic treap performs worst on a bad random sequence, while a deterministic treap performs worst on a bad set of keys. She wants to show Benjamin n integer keys that, when stored in his data structure, form a treap of height n, the most unbalanced case possible.

The input is a single integer n ($1 \le n \le 50000$).

Output n lines, each containing a distinct integer key. All keys must be between $-2^{31}$ and $2^{31} - 1$, inclusive. A treap built on these keys with the rule $y = \sin(x)$ must have height n.