Bài 4. Dãy ngoặc đúng (2 điểm)

Lam định nghĩa một chuỗi ngoặc chỉ gồm các kí tự ( và ) là đúng khi:

• Chuỗi rỗng là một chuỗi ngoặc đúng.
• Nếu A là một chuỗi ngoặc đúng thì (A) cũng là một chuỗi ngoặc đúng.
• Nếu A và B là một dãy ngoặc đúng thì AB cũng là một chuỗi ngoặc đúng.

Ví dụ, (()()) là một chuỗi ngoặc đúng, ()) không phải là một chuỗi ngoặc đúng.

Lam đưa ra một chuỗi S bao gồm các kí tự ( và ). Một chuỗi con của S là một dãy các kí tự liên tiếp của S.

Yêu cầu: Hãy giúp Lam đếm số chuỗi con liên tiếp của S là chuỗi ngoặc đúng.

Dữ liệu: Vào từ tệp văn bản BAI4.INP gồm một dòng ghi chuỗi S độ dài <= 10^6.

Kết quả: Ghi ra tệp văn bản BAI4.OUT một số nguyên là số lượng chuỗi con là chuỗi ngoặc đúng.

Ví dụ:

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm của bài có n <= 200;
• Có 50% số test tương ứng với 50% số điểm của bài có n <= 10^6.