Xóa đoạn ngoặc

Đị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à "))((" (từ vị trí $3$ đến vị trí $6$). 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.

Dữ liệu vào

• 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à ')'.

Dữ liệu ra

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

Ràng buộc

• $1\le N\le {10}^5$
• $S$ chỉ gồm các ký tự '(' và ')'

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 200$.
• Subtask 2 ($30\%$ số điểm): Chuỗi ban đầu là chuỗi ngoặc đúng.
• Subtask 3 ($20\%$ số điểm): $N\le 2000$.
• Subtask 4 ($20\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ