F. Два поддерева
ограничение по времени на тест
9 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано корневое дерево, состоящее из $$$n$$$ вершин. Корень находится в вершине $$$1$$$. В каждой вершине записано некоторое число: в $$$i$$$-й вершине — $$$val_i$$$.

Вы должны обработать $$$q$$$ запросов к дереву, $$$i$$$-й запрос задается двумя вершинами $$$u_i$$$ и $$$v_i$$$. Для ответа на запрос нужно рассмотреть все вершины $$$w$$$, которые лежат в поддереве $$$u_i$$$ или $$$v_i$$$ (если вершина лежит в обоих поддеревьях, она учитывается дважды). Нужно выписать все числа на вершинах в этой паре поддеревьев и найти то из них, которое встречается наибольшее количество раз (если таких несколько — минимальное из них).

Входные данные

В первой строке записано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве. Во второй строке записаны $$$n$$$ целых чисел $$$val_1, val_2, \dots, val_n$$$ ($$$1 \le val_i \le 2 \cdot 10^5$$$) — числа, записанные в вершинах.

Затем идет $$$n - 1$$$ строка, в каждой записаны по два числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$), представляющие ребро между вершинами $$$x$$$ и $$$y$$$. Данные ребра составляют дерево.

В следующей строке записано одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов, которые требуется обработать.

Затем идут $$$q$$$ строк, в $$$i$$$-й из них записаны два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — корни поддеревьев в $$$i$$$-м запросе.

Выходные данные

Для каждого запроса выведите ответ на него — целое число, которое встречается наибольшее количество раз в паре поддеревьев из запроса (если таких чисел несколько — минимальное из них).

Пример
Входные данные
8
2 1 3 2 3 3 2 4
1 2
1 3
2 4
3 5
3 6
3 7
7 8
6
2 7
3 7
2 3
1 1
5 6
1 3
Выходные данные
2
3
3
2
3
3
Примечание

В $$$1$$$-м запросе пара поддеревьев содержит вершины $$$[2, 4, 7, 8]$$$, на которых записаны числа $$$\{1, 2, 2, 4\}$$$. Число $$$2$$$ встречается дважды, все остальные — не более одного раза, поэтому ответ на запрос — $$$2$$$.

Во $$$2$$$-м запросе пара поддеревьев содержит вершины $$$[3, 5, 6, 7, 7, 8, 8]$$$, на которых записаны числа $$$\{3, 3, 3, 2, 2, 4, 4\}$$$. Число $$$3$$$ встречается наибольшее количество раз.

В $$$4$$$-м запросе пара поддеревьев содержит вершины $$$[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8]$$$, на которых записаны числа $$$\{2, 2, 1, 1, 3, 3, 2, 2, 3, 3, 3, 3, 2, 2, 4, 4\}$$$. Чаще всего встречаются числа $$$2$$$ и $$$3$$$, минимальное из них — $$$2$$$.