门户网站 cijepise.zdravlje.hr 是一个复杂的工程项目，旨在让克罗地亚共和国的居民能够登记接种 COVID-19 疫苗。该门户网站的开发成本超过四百万库纳，主要原因是它由一个顶尖的算法专家团队开发。

小安特（Ante）热爱编程、椰子冰淇淋并遵守流行病学措施。当然，他立即通过门户网站为他的 $Q$ 位密友登记了疫苗接种。他记得确切的日期，那是三月的第一天，他当时正在为即将到来的县级信息学竞赛做准备。在此期间，国家级竞赛已经结束，克罗地亚 Logo 奥林匹克竞赛也已举行，切尔西队也打进了欧冠决赛。然而，安特的任何一位朋友都没有收到疫苗接种邀请。

安特决定亲自处理这件事。他发送消息、打电话、拦截网络流量、编译和反编译。几个小时后，他弄清楚了门户网站的工作原理，并获得了所有用户的数据。现在他需要真正的算法专家的帮助。

门户网站的用户在内部存储为树状结构。也就是说，每一个 $N$ 个用户都由一个包含 $N$ 个节点的连通无环图（树）中的一个节点表示。树的节点用 $1$ 到 $N$ 的自然数标记，标记为 $1$ 的节点代表树的根。邀请用户接种疫苗的算法从向位于树根的用户发送接种邀请开始。该用户随后从系统中删除，此时树的根为空。随后是一个复杂的节点移动过程，持续整整 24 小时，之后下一个将被邀请的用户会出现在根节点。

复杂的节点移动过程首先将树的根与根节点年龄最大的子节点进行交换（swap）。现在树的根部有一个用户，而其子节点之一为空。然后，该过程将空子节点与其年龄最大的子节点进行交换，依此类推，直到树的叶子节点之一变为空。此时，该叶子节点从树中删除。此外，如果在过程的任何步骤中，某个节点有多个年龄最大的子节点，算法将随机选择其中一个年龄最大的子节点。

节点移动过程示例（数值对应用户的年龄）。

对于 $Q$ 位朋友中的每一位，安特想知道需要更改多少个用户的年龄，才能使该朋友以最少的接种天数获得接种资格。安特可以将任何用户的年龄更改为任何小于或等于 $2 \cdot 10^9$ 的非负整数。

输入格式

第一行包含题目描述中的自然数 $N$。

下一行包含 $N$ 个整数 $x_i$ ($1 \le x_i \le 10^9$)，依次表示用户的年龄。即 $x_i$ 对应位于标记为 $i$ 的节点上的用户的年龄。

在接下来的 $N-1$ 行中，每一行包含两个自然数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le N$)，表示标记为 $a_i$ 和 $b_i$ 的节点之间存在连接。

下一行包含题目描述中的自然数 $Q$。

在接下来的 $Q$ 行中，每一行包含一个自然数 $q_i$ ($1 \le q_i \le N$)，表示第 $i$ 位安特的朋友所在的节点标记。

输出格式

对于 $Q$ 行中的每一行，输出安特需要更改年龄的最少用户数，以便第 $i$ 位安特的朋友能在最少的天数内被邀请接种疫苗。

子任务

样例

样例 1

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

0
1
0

样例 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

0
1
1

样例 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

1
2
3