Cho một cây với ~n~ đỉnh. Mỗi đỉnh ~i~ có một giá trị ~a_i~ đi kèm với nó.

Giả sử ta chọn một đỉnh ~v~ làm gốc của cây. Đỉnh ~v~ được gọi là một gốc khác biệt nếu điều sau đây được thỏa mãn: trong tất cả các đường đi bắt đầu tại ~v~ và kết thúc tại một nút khác bất kỳ, tất cả các giá trị gặp trên đường đi đó đều phân biệt. Hai đường đi khác nhau có thể có các giá trị chung nhưng trên một đường đi đơn lẻ thì tất cả các giá trị phải phân biệt.

Hãy tìm số lượng gốc khác biệt trong cây.

Input

Dòng đầu tiên của đầu vào chứa một số nguyên duy nhất ~n~ ~(1 \le n \le 2 \cdot 10^5)~ - số lượng đỉnh trong cây.

Dòng tiếp theo chứa ~n~ số nguyên cách nhau bởi dấu cách ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách ~u~ và ~v~ ~(1 \le u, v \le n)~, biểu thị một cạnh nối từ ~u~ đến ~v~.

Đảm bảo rằng các cạnh tạo thành một cây.

Output

In ra một số nguyên duy nhất - số lượng gốc khác biệt trong cây.

Scoring

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

0

Notes

Test 1: ~1~, ~2~ và ~5~ là các gốc khác biệt.