printРабочее место участника

printЗадачи

1400. Дерево

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Одной из широко известных структур данных для представления множеств является двоичное дерево поиска. Каждый узел `v` такого дерева содержит один элемент множества, при этом все элементы в левом поддереве `v` должны быть меньше элемента в `v`, а элементы в правом поддереве `v` должны быть больше элемента в `v`. Пример двоичного дерева поиска показан на рисунке. Узел называется корнем, если у него нет родителя (узел 5 на рисунке). Узел называется листом, если у него нет детей (узлы 2, 4 и 8 на рисунке). Путём в дереве назовём последовательность номеров узлов, таких что каждый следующий узел является непосредственным потомком предыдущего.
11717.png
Вам дана последовательность неповторяющихся целых чисел. Требуется определить, существует ли такое двоичное дерево поиска, в котором эта последовательность является путём от корня к какому-то листу. Например, дерево поиска с путём 5-1-3-2 существует, а с путём 5-2-3-1 – нет.
Во входном файле содержится последовательность чисел, разделённых пробелами и/или переводами строк. До первого и после последнего числа могут быть пробелы и переводы строк. Все числа различны. Количество чисел от 1 до `50 000`. Значения чисел от `-2 147 483 648` до `2 147 483 647` включительно.
Выведите в выходной файл слово "YES", если дерево, соответствующее заданному пути, существует, и "NO" в противном случае.

Пример ввода 1

5 1 3 2

Пример вывода 1

YES

Пример ввода 2

5 2 3 1

Пример вывода 2

NO
Источник: XI Межвузовская олимпиада, г. Вологда, 2008
loading