Задача D1. Сбалансированное дерево revisited

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

Примечание: на текущий момент возможности CATS не позволяют автоматически распознать алгоритм решения задачи. В этой редакции предлагается решать задачу с использованием скип-листов или хэш-таблиц.

Формат входного файла

Входной файл содержит последовательность чисел.

Формат выходного файла

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1 3 0
1 2 3
2
5 -1 6 -5 5 0
5 6

0.122s 0.024s 15