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

Бинарное Дерево Поиска

Бинарное Дерево Поиска

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

Бинарное дерево поиска - это бинарное дерево со следующими свойствами:

  • Левое поддерево корня содержит вершины с ключами, меньшими ключа корня.

  • Правое поддерево корня содержит вершины с ключами, большими ключа вершины.

  • Левое и правое поддерево должны быть бинарными деревьями поиска.

prb3096

Прямой обход (Корень - Левое - Правое) выводит сначала ключ корня, а затем ключи левого и правого поддеревьев. Обратный обход (Левое - Правое - Корень) выводит сначала ключи левого поддерева, потом правого поддерева и корня. Результат прямого и обратного обхода для бинарного дерева, изображенного выше на рисунке, имеет вид:

Прямой обход: 50 30 24 5 28 45 98 52 60

Обратный обход: 5 28 24 45 30 60 52 98 50

По заданному прямому обходу бинарного дерева поиска следует найти порядок вершин при обратном обходе.

Вхідні дані

Ключи всех вершин бинарного дерева поиска заданы в порядке его прямого обхода. Ключ каждой вершины является натуральным значением, меньшим 10^6. Все значения заданы в разных строках (по одному числу в строке). Бинарное дерево содержит не более 10.000 вершин и не содержит вершин с одинаковыми ключами.

Вихідні дані

Вывести обратный обход дерева. Каждый ключ следует выводить в отдельной строке.

Приклад

Вхідні дані #1
50
30
24
5
28
45
98
52
60
Вихідні дані #1
5
28
24
45
30
60
52
98
50
Джерело 2011 ACM-ICPC Asia Phuket Regional Programming Contest, Ноябрь 4