Distinct weights on a tree path

Time limit2sMemory limit512 MB

Level: Not classified yet
Solved: No attempts yet

Problem

You are given a tree with $N$ vertices. A tree is a connected undirected graph with no cycle. The vertices are numbered from 1 to $N$ and the edges are numbered from 1 to $N-1$ . Every vertex carries one weight.

Write a program that answers the following query.

u v: print how many different weight values appear among the vertices on the path from vertex $u$ to vertex $v$ . The path includes both endpoints $u$ and $v$ .

Input

The first line contains the number of vertices $N$ . ( $2 \le N \le 100000$ )

The second line contains the weights of vertices 1 through $N$ in order. Every weight is a positive integer no larger than $1000000$ .

Each of the next $N-1$ lines contains two vertex numbers $u$ and $v$ joined by edge $i$ . The given edges always form a single tree.

The next line contains the number of queries $M$ . ( $1 \le M \le 100000$ )

Each of the next $M$ lines contains one query in the form u v. Both $u$ and $v$ are between 1 and $N$ , and queries where the two values are equal also occur.

Output

Print the answer to each query on its own line, in the order the queries are given.

Examples3

Example 1

Input

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

Expected output

4
4

Example 2
Input
```
2
7 7
1 2
4
1 1
2 2
1 2
2 1
```
Expected output
```
1
1
1
1
```

Example 3

Input

10
10 20 30 40 50 60 70 80 90 100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
5
1 10
5 5
4 7
10 1
2 9

Expected output