ami có một đồ thị dạng cây gồm \(n\) nút, mỗi nút được đánh số từ 1. Nút \(i\) được tô màu \(a_i\).

ami cần các bạn tính tổng tất cả đường đi ngắn nhất giữa hai nút u và v được tô cùng một chung màu. Tổng có thể được biểu diễn như sau:

\(\sum dist(u , v)\) \(\forall\) \(u \leq v\) và \(a_u = a_v\).

Trong đó, \(dist(u , v)\) là độ dài đường đi ngắn nhất giữa hay nút \(u\) và \(v\). Độ dài một đường đi từ u đến v được tính bằng tổng số cạnh nằm trên đường đi đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số đỉnh của cây.

• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) biểu thị một màu của đỉnh \(i\).

• \(n\) dòng tiếp theo, môi dòng chứa \(2\) số nguyên dương \(u\) và \(v\) biểu thị một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

• Hãy in ra tổng cần tìm

Scoring

• Subtask \(1\) (\(18\%\) số điểm): \(1 \leq n \leq 10\) và \(1 \leq a_i \leq 3*10^5\).

• Subtask \(2\) (\(18\%\) số điểm): \(1 \leq n \leq 1000\) và \(1 \leq a_i \leq 3*10^5\).

• Subtask \(3\) (\(18\%\) số điểm): \(1 \leq n \leq 3*10^5\) và \(1 \leq a_i \leq 10\).

• Subtask \(4\) (\(46\%\) số điểm): \(1 \leq n \leq 3*10^5\) và \(1 \leq a_i \leq 3*10^5\).

Example

4
1 3 1 3
1 2
2 3
2 4

3

9
1 1 1 2 3 2 2 1 1 
1 2
2 3
3 4
3 5
4 6
3 7
7 8
7 9

30