e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

By steps of 2019 ACM NEERC, Bad Treap

Плохой Treap

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 строк содержащих различные целочисленные ключи. Все ключи должны лежать в интервале между -231 и 2311 включительно. Декартово дерево, построенное на ключах по правилу y = sin(x), должно иметь высоту n.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
Выходные данные #1
-2
0
-1
-4
Источник 2019 ACM NEERC, Северный регион, Октябрь 26, Задача B