彼得准备举办一个生日聚会，他决定邀请他担任 CEO 的公司中的一些员工参加。

包括彼得在内的每位员工都有一个唯一的编号（从 $1$ 到 $N$），以及他们所讲的笑话类型 $V_i$。此外，除彼得外，公司中的每位员工都恰好有一位直属上司。 由于彼得是公司的 CEO，他的编号为 $1$，并且是所有员工的直接或间接上司。

在生日聚会上，所有到场的人（包括彼得）都必须遵守以下规则：

• 聚会上不能有两个人讲同一种类型的笑话。
• 如果某人 $X$ 的直属上司没有被邀请，则 $X$ 也不能被邀请。
• 如果被邀请的人中，以 $X$ 为首的子树中所有被邀请的人（包括 $X$ 本人）所讲的笑话类型集合不能构成一组连续的数字，则 $X$ 不能被邀请。

如果一个集合在升序排序后，相邻元素之间的差值恰好为 $1$，则称该集合中的数字是连续的。例如，$\{3, 1, 2\}$ 和 $\{5, 1, 2, 4, 3\}$。

彼得想知道，在上述限制条件下，他在聚会上能看到多少种不同的笑话类型集合。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 10\,000$）。

输入的第二行包含 $N$ 个整数，表示第 $i$ 个人所讲的笑话类型 $V_i$（$1 \le V_i \le 100$）。

接下来的 $N-1$ 行，每行包含两个整数 $A$ 和 $B$（$1 \le A, B \le N$），表示 $A$ 是 $B$ 的直属上司。

输出格式

输出的唯一一行应包含符合上述限制条件的不同的笑话类型集合的数量。

数据范围

对于占总分 $50\%$ 的测试数据，满足 $N$ 不超过 $100$。

样例

输入样例 1

4 
2 1 3 4 
1 2 
1 3 
3 4

输出样例 1

6

输入样例 2

4 
3 4 5 6 
1 2 
1 3 
2 4

输出样例 2

3

输入样例 3

6 
5 3 6 4 2 1 
1 2 
1 3 
1 4 
2 5 
5 6

输出样例 3

10

说明

样例 1 解释

在聚会上可能会出现以下笑话类型集合： $\{2\}$，$\{2, 3\}$，$\{2, 3, 4\}$，$\{1, 2, 3, 4\}$，$\{1, 2\}$，$\{1, 2, 3\}$。

样例 2 解释

唯一可能的笑话类型集合为：$\{3\}$，$\{3, 4\}$，$\{3, 4, 5\}$。 注意，讲笑话 $6$ 的人（员工 $4$）不能参加聚会，因为在这种情况下，以员工 $2$ 为首的子树中被邀请者所讲的笑话集合 $\{4, 6\}$ 不是一组连续的数字。