Định nghĩa chuỗi ngoặc đúng:

• Chuỗi rỗng là chuỗi ngoặc đúng;

• Nếu ~X~ là chuỗi ngoặc đúng thì ~(X)~ cũng là chuỗi ngoặc đúng;

• Nếu ~X~ và ~Y~ là hai chuỗi ngoặc đúng thì ~XY~ cũng là chuỗi ngoặc đúng.

Ví dụ:

• Chuỗi ngoặc đúng: "", "()", "(())", "()()", "(())()()",...;

• Chuỗi ngoặc không đúng: "(", "()(", "())(", ")()(",...

Cho chuỗi ~S~ có độ dài ~N~, chỉ gồm hai loại ký tự '(' và ')'. Chọn hai số nguyên dương ~L~ và ~R~ ~(1 \le L \le R \le N)~, xoá tất cả các ký tự từ vị trí thứ ~L~ đến vị trí thứ ~R~ của chuỗi ~S~.

Ví dụ: ~S =~ "(())(())". Chọn ~L = 3~ và ~R = 6~; đoạn cần xoá là đoạn ký tự được gạch giữa trong chuỗi. Chuỗi ~S~ sau khi xoá: ~S =~ "(())".

Yêu cầu: Hãy đếm số cách chọn ~L, R~ để chuỗi sau khi xoá là một chuỗi ngoặc đúng.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^5)~;

• Dòng thứ hai chứa xâu ~S~ gồm ~N~ ký tự '(' và ')'.

Output

• Một số nguyên dương là kết quả bài toán.

Scoring

Sample Input 1

5
())()

Sample Output 1

6

Sample Input 2

4
(())

Sample Output 2

2

Notes

Các cách xoá thoả mãn trong ví dụ 1:

• ~L = 1, R = 5~: ~S =~ "";

• ~L = 1, R = 3~: ~S =~ "()";

• ~L = 2, R = 4~: ~S =~ "()";

• ~L = 3, R = 5~: ~S =~ "()";

• ~L = 2, R = 2~: ~S =~ "()()";

• ~L = 3, R = 3~: ~S =~ "()()".

Các cách xoá thoả mãn trong ví dụ 2:

• ~L = 1, R = 4~: ~S =~ "";

• ~L = 2, R = 3~: ~S =~ "()".