测试数据来自 nnu_contest/1098

描述

有一张n个点的树，点的标号是1~n，第i个点的点权为wi。Q次询问，每次询问两个点，求在这两点间的最短路径上完成一次贸易的最大利润（在一个点买入价格为其点权的商品，在后面的一个点卖出）。输入中第一行为n，后面n行，每行一个数为每个点的点权，后面n-1行，每行两个数a,b，表示一条树边(a,b)，接下来单行输入一个数为Q，后面Q行，每行两个数表示路径的起点和终点。

输入样例

4
1 
5 
3 
2
1 3
3 2
3 4
9
1 2
1 3
1 4
2 3
2 1
2 4
3 1
3 2
3 4

输出样例

4
2
2
0
0
0
0
2
0

样例解释

对于第一个询问，在一号点以1的价格买入，在二号点以5的价格卖出，获利为4。
后面的询问以此类推。

时空限制

每个测试点1s
空间65536KB

数据范围

对于100%的数据，满足1<=n，Q，wi<=50000