Общий предок в дереве поиска
Отправить решение
Решать в редакторе
Сложность:
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
Комментарии