题目描述

穷愁潦倒的小 B 正在树上漫步，突然接到了小 S 的电话，要他去点 $y$ 买一些礼物，然而他现在正处于 $x$ 点，并且他身上并没有钱。

小 L 告诉了他一个绝妙的方法。树上的每个点都有大佬的存在，其中一些大佬会购买或出售（售价与收购价相同）bsoj 权限账号。而且各点 dalao 数量不同，价格也不同，这样的交易能使他赚上一笔差价。小 S 没有告诉他礼物的价钱，他只能赚尽量多的钱。由于小 S 在小 B 的身上装了追踪器，所以他只能走 $x$ 到 $y$ 的最短路，而且时间不足，因此这样的交易只能发生一次（指买一次卖一次）。

小 B 这样的大神犇显然已经知道求解方法了，但他为了不被小 S 发现，让你来帮他解决这个问题。

输入格式

输入第一行是一个整数 $n$，表示树上的点数。
接下来 $n$ 个正整数，表示每个点上权限号的价格。
接下来 $n-1$ 行， 每行两个整数 $x, y$，表示第 $x$ 点和第 $y$ 点有一条边。
接下来一个整数 $m$，表示接下来有 $m$ 个询问。
接下来有 $m$ 行， 每行两个整数 $x$ 和 $y$，表示小 B 从第 $x$ 点出发要到第 $y$ 点。

输出格式

输出包括 $m$ 行。 每行对应一个询问，一个整数， 表示小 B 最多能赚到多少钱。

样例

input

10
3 4 1 2 7 6 1 5 3 9
1 2
1 9
3 1
9 7
5 9
6 9
8 7
4 7
10 7
3
5 6
8 10
2 4

output

3
8
1

数据范围与提示

对于 $40\%$ 的数据，$1\le n,m\le 10^3$；
对于全部数据，$1\le n,m\le 2.5\times 10^5$。