В дереві у кожної вершини є своя ціна. Необхідно відповідати на запити знаходження найменшої ціни на шляху між двома вершинами.

Формат вхідних даних

В першому рядку число \(N\) - кліькість вершин дерева (\(1 \le N \le 2*10^5\))
В другому рядку \(N\) чисел \(Ci\) - ціни відповідних вершин дерева (\(0 \le Ci \le 10^9\))
В кожному з наступних \(N\) рядків по два числа \(v1,v2\) які описують ребро дерева \((v1,v2)\) (\(1 \le v1,v2 \le N\)),
В четвертому рядку число \(M\) - кількість запитів (\(1 \le M \le 2*10^5\))
В кожному з наступних \(M\) рядків по два числа \(q1,q2\) - номера вершин для яких необхідно обчислити відстань (\(1 \le q1,q2 \le N\))

Формат вихідних даних

Для кожного запиту виведіть в окремому рядку відповідь - найменшу ціну на шляху між відповідними вершинами

Приклад вхідних даних

5
3 2 1 7 2
1 2
1 3
2 4
2 5
4
3 4
5 4
5 1
2 2

Приклад вихідних даних

1
2
2
2