Dãy ngoặc đúng

Bạn được cho một cây có \(n\) đỉnh. Mỗi đỉnh trên cây được gán một ký tự là một dấu ngoặc đơn, có thể là ( hoặc ).

Một đường đi đơn giữa hai đỉnh \(u\) và \(v\) tạo ra một chuỗi ngoặc bằng cách ghép các ký tự ngoặc của các đỉnh trên đường đi theo thứ tự. Chuỗi ngoặc này được coi là hợp lệ nếu:

• Tổng số dấu ngoặc mở bằng tổng số dấu ngoặc đóng.
• Với bất kỳ tiền tố nào của chuỗi, số dấu ngoặc mở không nhỏ hơn số dấu ngoặc đóng.

Hãy tìm và đếm số cặp đỉnh \((u, v)\) (với \(u\) và \(v\) là hai đỉnh bất kỳ trên cây) sao cho chuỗi ngoặc được tạo từ đường đi giữa chúng là một chuỗi ngoặc hợp lệ.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 3 \cdot 10^5\)), là số đỉnh của cây.
• Dòng thứ hai chứa \(n\) ký tự \(s_1, s_2, \ldots, s_n\) (\(s_i \in \{'(', ')'\}\)), trong đó \(s_i\) là ký tự ngoặc tại đỉnh thứ \(i\).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n, u \ne v\)), biểu thị một cạnh nối giữa hai đỉnh \(u\) và \(v\).

Output

In ra một số nguyên duy nhất là tổng số cặp đỉnh \((u, v)\) thỏa mãn yêu cầu.

Example

6
()()()
1 2
2 3
3 4
3 5
5 6

5

Scoring

• Subtask 1 (30 điểm): \(2 \le n \le 5000\).
• Subtask 2 (70 điểm): Không có ràng buộc bổ sung.