H. Почтовая реформа

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

Курьеру, который развозит посылки во все города на пути от $i$ до $j$ включительно, нужна верёвка длиной не меньше самой высокой башни на этом пути. Обрабатывайте запросы:

• ! i h — высота башни в городе $i$ стала равна $h$;
• ? i j — какой длины верёвка нужна курьеру.

В первой строке — число $n$ ($1 \le n \le 5 \cdot 10^4$). Во второй — $n$ чисел: высоты башен ($1 \le h_i \le 10^5$). В следующих $n - 1$ строках — пары $u$, $v$: дороги. Далее число запросов $k$ ($1 \le k \le 10^5$) и сами запросы; $1 \le i, j \le n$, $1 \le h \le 10^5$.

На каждый запрос ? выведите нужную длину верёвки.