测试数据来自 system/1288

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

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

　　小 L 告诉了他一个绝妙的方法。树上的每个点都有大佬的存在，其中一些大佬会购买或出售（售价与收购价相同）OJ 权限账号。而且各点大佬数量不同，价格也不同，这样的交易能使他赚上一笔差价。小 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≤n,m≤100\)；
　　对于全部数据，\(1≤n,m≤250000\)。

【来源】

　　Mr.he