一天，你们wyh学长和你们zhl学长玩一个游戏，这个游戏规则是这样的
给你n个城市，保证这n个城市之间都只有一条道路可以到达。
有一件物品，在所有城市中都是一样的，但是由于各个城市的经济发展不同，导致每个城市对于这件物品销售的价格不同。
游戏一共进行Q轮。
每轮给你2个点s和t，其中s代表起点，t代表终点。
对于每一个城市都可以选择买这个物品，如果手里有这个物品的话，也可以选择卖掉这个物品，对于同一个城市来说，买和卖的价格是一样的，每一个城市只能买一件物品
现在，你们wyh学长和zhl学长都需要找到一个方案，使得从起点走到终点的时候盈利最多，请你帮助帮助他们吧
每个测试文件中都只有一组测试数据
输入第一行一个整数n(1<=n<=50000)，代表有n个城市
第二行输入n个数，代表每个城市对于这件物品的价格wi(1<=wi<=50000)
接下来有n-1行，每行2个数a和b，代表a到b之间有一条路
接下来输入一个数Q(1<=Q<=50000)
接下来Q行，每行2个数s和t
对于每组测试数据，输出对应答案，如果从起点到终点不能盈利的话，输出0