Cijepise

Portal cijepise.zdravlje.hr is a technical project that lets residents of the Republic of Croatia sign up for vaccination against COVID-19. The portal cost a little over four million kuna, mainly because a top team of algorithm experts worked on it.

Little Ante loves programming, coconut ice cream, and following epidemic measures. Of course, he immediately signed his $Q$ close friends up for vaccination through the portal. He remembers the exact date: it was March 1st, and he was preparing for the county informatics competition. In the meantime the national competition took place, 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 the help line, intercepted network traffic, and compiled and decompiled code. After a few hours he worked out how the portal runs and gained access to the data of all users. Now he needs help from real algorithm experts.

Users are stored internally in a tree. Each of the $N$ users is one of $N$ nodes of a simple connected graph with $(N - 1)$ edges. Nodes are labeled with natural numbers from $1$ to $N$, and node $1$ is the root. The invitation algorithm starts by sending an invitation to the user at the root. That user is removed from the system, and the root becomes empty. Then a complicated node-moving procedure runs for exactly 24 hours, after which the next user to be invited appears at the root.

The node-moving procedure first swaps the root with its child of the greatest age. Now the root holds some user, and one of its children is empty. Then the procedure swaps the empty child with its oldest child, and so on, until one of the leaves becomes empty. That leaf is then removed from the tree. If at any step a node has several children of the same greatest age, the algorithm picks one of the oldest children at random.

An example of the node-moving procedure (values are user ages).

For each of the $Q$ friends, Ante wants the minimum number of users whose age he must change so that that friend is invited with certainty in the smallest possible number of days. Ante can change a user's age to any non-negative integer less than or equal to $2 \cdot 10^9$.

The first line contains the natural number $N$ from the statement.

The second line contains $N$ integers $x_i$ ($1 \le x_i \le 10^9$), where $x_i$ is the age of the user at node $i$.

Each of the next $N - 1$ lines contains natural numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N$), meaning there is an edge between nodes $a_i$ and $b_i$.

The next line contains the natural number $Q$ from the statement.

Each of the next $Q$ lines contains a natural number $q_i$ ($1 \le q_i \le N$), the node where the $i$-th friend is located.

For each of the $Q$ friends, print on its own line the minimum number of users whose age Ante must change so that the $i$-th friend is invited in the smallest possible number of days.