Truy vấn ngoặc cân bằng trên đoạn

Bối cảnh và bài toán

Một chuỗi cấu hình chỉ gồm ( và ). Với mỗi đoạn con được hỏi, hệ thống cần xác định độ dài lớn nhất của một dãy con (giữ nguyên thứ tự nhưng có thể bỏ ký tự) tạo thành chuỗi ngoặc đúng.

Yêu cầu

Trả lời độc lập từng truy vấn đoạn.

Input

• Dòng 1 chứa chuỗi s.
• Dòng 2 chứa q.
• q dòng tiếp theo chứa l r.

Output

Với mỗi truy vấn, in độ dài dãy con ngoặc đúng dài nhất nằm trong s[l..r].

Ràng buộc

• 1 <= \|s\| <= 2 * 10^5
• 1 <= q <= 10^5
• 1 <= l <= r <= \|s\|

Chấm điểm

Ví dụ 1

Input

())(())(())(
4
1 1
1 12
5 11
2 10

Output

0
10
6
6

Giải thích. Mỗi đáp án là hai lần số cặp ngoặc có thể ghép theo đúng thứ tự.

Ví dụ 2

Input

)()(()
3
1 6
2 3
4 6

Output

4
2
2

Giải thích. Các ngoặc dư không bắt cặp được sẽ bị bỏ khỏi dãy con.

Thông tin bài tập

• Yêu cầu ngoài OJ: nộp Decision Note theo template đi kèm.

Nguồn: Phỏng theo Codeforces 380C – Sereja and Brackets.