Nông dân John có \(N\) con bò (\(2 \leq N \leq 10^5\)). Mỗi con bò thuộc một giống bò Guernsey hoặc Holstein. Như thường lệ, các con bò đứng thành một hàng, được đánh số từ \(1\) đến \(N\) theo thứ tự này.

Trong suốt cả ngày, mỗi con bò sẽ viết ra một danh sách các con bò. Cụ thể, danh sách của con bò thứ \(i\) chứa các con bò từ chính con bò đó (con bò \(i\)) đến con bò \(E_i\) (\(i \leq E_i \leq N\)).

John vừa phát hiện ra rằng mỗi giống bò có đúng một lãnh đạo riêng biệt. John không biết chính xác con nào là lãnh đạo, nhưng anh biết rằng mỗi lãnh đạo phải có một danh sách mà bao gồm tất cả các con bò cùng giống của nó hoặc lãnh đạo của giống bò khác (hoặc cả hai).

Hãy giúp John đếm số cặp có thể là lãnh đạo. Đảm bảo rằng luôn có ít nhất một cặp có thể là lãnh đạo.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa một chuỗi có độ dài \(N\), với ký tự thứ \(i\) biểu thị giống của con bò thứ \(i\) (G có nghĩa là Guernsey và H có nghĩa là Holstein). Đảm bảo rằng luôn có ít nhất một con bò Guernsey và một con bò Holstein.
• Dòng thứ ba chứa các số nguyên \(E_1, \dots, E_N\).

Output

• In ra số lượng cặp có thể là người lãnh đạo.

Scoring

• Subtask 1: \(N \leq 100\).
• Subtask 2: \(N \leq 3000\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

4
GHHG
2 4 3 4

1

3
GGH
2 3 3

2