Задача D. Почтовая реформа

Входной файл:mail.in   Ограничение времени:4 сек
Выходной файл:mail.out   Ограничение памяти:256 Мб

Условие

В Флатландии идет пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причем только одним способом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.

Недавно образованное почтовое агентство "Экс-Федя" предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h, курьеру агентства требуется иметь с собой не менее h метров веревки.

Вам поручено руководить отделом логистики — по имеющимся данным о высотах башен и об их изменениях вам нужно определять минимальную длину веревки, которую нужно выдать курьеру, который доставляет посылки между городами i и j.

Формат входного файла

Первая строка входного файла содержит число n — количество городов в Флатландии (1 ≤ n ≤ 50000). Во второй строке находится n положительных чисел, не превосходящих 105 — высоты башен в городах. В следующих n − 1 строках содержится по два числа ui и vi — описание i-й дороги, 1 ≤ ui, vi ≤ n, ui ≠ vi. В следующий строке содержится число k — количество запросов (1 ≤ k ≤ 100000). В следующих k строках содержатся описания запросов в следующем формате:

Формат выходного файла

Для каждого запроса доставки посылок выведите минимальную длину веревки, которую необходимо выдать курьеру.

Примеры тестов

Входной файл (mail.in) Выходной файл (mail.out)
1
3
1 2 3
1 3
2 3
5
? 1 2
! 1 5
? 2 3
! 3 2
? 1 2
3
3
5
2
1
100
5
! 1 1
? 1 1
! 1 1000
? 1 1
! 1 1
1
1000

0.079s 0.016s 13