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