The portal cijepise.zdravlje.hr is a complex technical project that allows residents of the Republic of Croatia to register for COVID-19 vaccination. The development of the portal cost a little over four million kuna, and the main reason for this is the fact that a top team of algorithmic experts worked on it.

Little Ante loves programming, coconut ice cream, and following epidemiological measures. Naturally, he immediately registered his $Q$ close friends for vaccination via the portal. He remembers the exact date; it was the first day of March, and he was preparing for the upcoming county informatics competition. In the meantime, the national competition passed, the Croatian Logo Olympiad was held, and Chelsea reached the Champions League final. However, none of Ante's friends received a vaccination invitation.

Ante decided to take matters into his own hands. He sent messages, called people, intercepted network traffic, compiled, and decompiled. After a few hours, he concluded how the portal works and gained access to all user data. Now he needs the help of real algorithmic experts.

The portal's users are stored internally in a tree structure. Specifically, each of the $N$ users is represented by one of the $N$ nodes of a simple, connected graph with $N-1$ edges. The tree nodes are labeled with natural numbers from $1$ to $N$, and the node labeled $1$ represents the root of the tree. The algorithm used to invite users for vaccination begins by sending a vaccination invitation to the user located at the root of the tree. This user is then deleted from the system, and the root of the tree is now empty. This is followed by a complex node-shifting process that lasts exactly 24 hours, after which the next user to be invited will appear at the root.

The complex node-shifting process first swaps the root of the tree with its child of the greatest age. Now, some user is at the root of the tree, and one of their children is empty. Then, the process swaps the empty child with its oldest child, and so on, until one of the leaves of the tree becomes empty. At that point, that leaf is deleted from the tree. Additionally, if at any step of the process a node has multiple children of the same greatest age, the algorithm will randomly choose the oldest child.

Example of the node-shifting process (values correspond to user ages).

For each of the $Q$ friends, Ante is interested in the minimum number of users whose age needs to be changed so that this friend would be called for vaccination in the minimum number of days with one hundred percent certainty. Ante can change the age of any user to any non-negative integer less than or equal to $2 \cdot 10^9$.

Input

The first line contains a natural number $N$.

The next line contains $N$ numbers $x_i$ ($1 \le x_i \le 10^9$) which represent the ages of the users in order. That is, $x_i$ corresponds to the age of the user located at the node labeled $i$.

In each of the next $N-1$ lines, there are natural numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$) indicating that there is a connection between the nodes labeled $a_i$ and $b_i$.

The next line contains a natural number $Q$.

In each of the next $Q$ lines, there is a natural number $q_i$ ($1 \le q_i \le N$) representing the label of the node where the $i$-th friend of Ante is located.

Output

In the $i$-th of $Q$ lines, print the minimum number of users whose age Ante needs to change so that the $i$-th friend of Ante is called for vaccination in the minimum number of days.

Subtasks

Examples

Input 1

3
1 2 3
1 2
1 3
3
1
2
3

Output 1

0
1
0

Input 2

7
45 13 19 3 81 27 77
1 2
1 3
1 4
3 5
3 6
4 7
3
5
6
7

Output 2

0
1
1

Input 3

8
23 4 9 7 11 4 1 18
2 1
3 2
4 2
5 2
6 3
7 4
8 1
3
2
3
7

Output 3

1
2
3