Xóa đoạn ngoặc (Delete Bracket Segment)

Nguồn: Sở Giáo dục và Đào tạo Hà Nội — Kỳ thi chọn HSG thành phố và chọn đội tuyển HSG dự thi Olympic quốc gia các môn văn hóa, lớp 12 THPT năm học 2026–2027, môn Tin học (Bảng A)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một chuỗi ngoặc đúng được định nghĩa như sau:

• Chuỗi rỗng là một chuỗi ngoặc đúng.
• Nếu $X$ là một chuỗi ngoặc đúng thì $(X)$ cũng là một chuỗi ngoặc đúng.
• Nếu $X$ và $Y$ là hai chuỗi ngoặc đúng thì $XY$ cũng là một chuỗi ngoặc đúng.

Cho chuỗi $S$ có độ dài $N$, chỉ gồm hai ký tự ( và ).

Chọn hai số nguyên $L$ và $R$ thỏa mãn

sau đó xóa toàn bộ các ký tự từ vị trí thứ $L$ đến vị trí thứ $R$ của chuỗi $S$.

Hãy đếm số cách chọn cặp $(L,R)$ sao cho chuỗi còn lại sau khi xóa là một chuỗi ngoặc đúng.

Input

• Dòng đầu tiên chứa số nguyên dương $N$.
• Dòng thứ hai chứa chuỗi $S$ gồm đúng $N$ ký tự ( và ).

Output

In ra một số nguyên duy nhất là số cách chọn $(L,R)$ thỏa mãn yêu cầu.

Subtask

• Subtask 1 — 20 điểm: $1 \le N \le 100$.
• Subtask 2 — 30 điểm: $1 \le N \le 3000$.
• Subtask 3 — 50 điểm: $1 \le N \le 10^5$.

Ví dụ

Ví dụ 1

Input

5
())()

Output

6

Giải thích

Có $6$ cách xóa thỏa mãn, tương ứng với các cặp $(L,R)$:

• $(1,5)$: xóa toàn bộ chuỗi, còn chuỗi rỗng;
• $(1,3)$: còn ();
• $(2,4)$: còn ();
• $(3,5)$: còn ();
• $(2,2)$: còn ()();
• $(3,3)$: còn ()().

Ví dụ 2

Input

4
(())

Output

2

Giải thích

Hai cách xóa thỏa mãn là:

• $(1,4)$: xóa toàn bộ chuỗi, còn chuỗi rỗng;
• $(2,3)$: còn ().