Общий предок в дереве поиска


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Общий предок в дереве поиска

Двоичное дерево поиска строится так: первое число — корень; каждое следующее спускается от корня, влево если оно меньше значения в вершине, иначе вправо, и становится новым листом. Для q пар значений a, b, присутствующих в дереве, найдите значение их наименьшего общего предка (вершина — предок самой себя).

Ввод. В первой строке n и q. Во второй — n различных чисел в порядке добавления. Затем q строк с парами a b. 1 ≤ n ≤ 2000, 1 ≤ q ≤ 5000.

Вывод. Для каждой пары — значение в отдельной строке.

Примеры

Ввод 1

5 2
4 2 6 1 3
1 3
1 6

Вывод 1

2
4

Комментарии

Еще нет ни одного комментария.