Petar is throwing a birthday party and he decided to invite some of the employees of his company where he is the CEO.

Each employee, including Petar, has a unique label from ~1~ to ~N~, and an accompanying type of jokes they tell ~V_i~. Also, each employee of the company except Petar has exactly one supervisor.

Since Petar is the CEO of the company, he has the label ~1~ and is directly or indirectly superordinate to all the employees.

At the birthday party, there are certain rules that all people present (including Petar) must follow.

• At the party, there shouldn't be two people that tell the same type of jokes.
• Person ~X~ cannot be invited if their direct supervisor is not invited.
• Person ~X~ cannot be invited if the set of jokes the invitees that person ~X~ is superior to (directly or indirectly) tell and person ~X~ don't form a set of consecutive numbers. The numbers in the set are consecutive if the difference between adjacent elements is exactly 1 when the set is sorted ascendingly. For example, ~(3, 1, 2)~ and ~(5, 1, 2, 4, 3)~.

Petar wants to know how many different sets of jokes he can see at his party with the listed constraints.

Input Specification

The first line of input contains the integer ~N~ ~(1 \le N \le 10\,000)~.

The second line of input contains ~N~ integers, the types of jokes person ~i~ tells, ~V_i~ ~(1 \le V_i \le 100)~.

Each of the following ~N-1~ lines contains two integers ~A~ and ~B~ ~(1 \le A, B \le N)~, denoting that person ~A~ is directly superior to person ~B~.

In test cases worth 50% of total points, it will hold that ~N~ does not exceed ~100~.

Output Specification

The first and only line of output must contain the number of different sets of jokes that comply to the previously listed constraints.

Sample Input 1

4
2 1 3 4
1 2
1 3
3 4

Sample Output 1

6

Explanation of Sample Output 1

It is possible to have the following sets of jokes at the party:

~\{2\}~, ~\{2, 3\}~, ~\{2, 3, 4\}~, ~\{1, 2, 3, 4\}~, ~\{1, 2\}~, ~\{1, 2, 3\}~.

Sample Input 2

4
3 4 5 6
1 2
1 3
2 4

Sample Output 2

3

Explanation for Sample Output 2

The only possible sets of jokes are: ~\{3\}~, ~\{3, 4\}~, ~\{3, 4, 5\}~. Notice that the person telling joke ~6~ cannot be at the party because, in that case, the set of jokes ~\{4, 6\}~ is not a set of consecutive numbers.

Sample Input 3

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

Sample Output 3

10