# The merchant

Time Limit: 3000MS

Memory Limit: 65536K

## Description

There are N cities in a country, and there is one and only one simple path between each pair of cities. A merchant has chosen some paths and wants to earn as much money as possible in each path. When he move along a path, he can choose one city to buy some goods and sell them in a city after it. The goods in all cities are the same but the prices are different. Now your task is to calculate the maximum possible profit on each path.

## Input

The first line contains N, the number of cities. Each of the next N lines contains wi the goods' price in each city. Each of the next N-1 lines contains labels of two cities, describing a road between the two cities. The next line contains Q, the number of paths. Each of the next Q lines contains labels of two cities, describing a path. The cities are numbered from 1 to N. 1 ≤ N, wi, Q ≤ 50000

## Output

The output contains Q lines, each contains the maximum profit of the corresponding path. If no positive profit can be earned, output 0 instead.

## Sample Input

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

## Sample Output

4
2
2
0
0
0
0
2
0


## Source

POJ Monthly Contest – 2009.04.05, GaoYihan