eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Плохой Treap

Плохой Treap

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Treap, известное как декартово дерево, представляет собой структуру данных, которая хранит набор ключей в бинарном дереве поиска.

Каждая вершина дерева характеризуется парой (x, y).

x значения вершин - значения сохраненных ключей. Они удовлетворяют правилу "поиска в бинарном дереве": все x значения левого поддерева меньше значения x в корне, а все x значения правого поддерева больше значения x в корне.

y значения вершин удовлетворяют правилу "кучи": y значение вершины меньше или равно y значению родителя.

y значение для каждого созданного узла обычно выбирается случайным образом в соответствии с некоторым распределением. Это приводит к хорошей средней временной сложности многих операций.

Поскольку эта структура данных объединяет некоторые свойства двоичного дерева поиска и кучи, ее имя является термином "portmanteau", состоящим из двух слов: TRee + hEAP = TREAP.

prb9519.gif

Бенджамин решил, что недетерминизм в процедуре выбора значения y является плохим, поскольку в этом случае время выполнения запросов различно. Он решил рассчитать y для каждого узла детерминировано на основе его значения x. Он выбрал правило y = sin(x). Бенджамин особенно рад, что различные целые числа x всегда будут давать различные y.

Барбара понимает, что хотя недетерминированное декартово дерево показывает худшую производительность, когда предоставляется "плохая" случайная последовательность, детерминированное декартово дерево показывает худшую производительность, когда предоставляется "плохой" набор ключей. Она хочет объяснить это Бенджамину, показав ему n целочисленных ключей, которые, будучи сохраненными в его структуре данных, сформируют дерево высоты n - "наиболее несбалансированную" возможную ситуацию.

Помогите Барбаре предоставить n таких ключей. Все эти ключи должны помещаться в 32 - битовый знаковый тип.

Вхідні дані

Одно целое число n (1n50 000).

Вихідні дані

Выведите n строк содержащих различные целочисленные ключи. Все ключи должны лежать в интервале между -2^31 и 2^311 включительно. Декартово дерево, построенное на ключах по правилу y = sin(x), должно иметь высоту n.

Приклад

Вхідні дані #1
4
Вихідні дані #1
-2
0
-1
-4
Джерело 2019 ACM NEERC, Северный регион, Октябрь 26, Задача B