{"code":"bracket","name":"Tổng Ngoặc Đúng","description":"Ơ trong 1 lần đi chơi với đám bạn (Khánh, Hòa, Khoa, Quân, Ngạn), cả 5 thanh niên này đều muốn chơi game, nhưng mà ai cũng không có tiền nhưng cạnh bên quán game lại có 1 cô gái tên là Thảo, cô gái này đưa ra nhưng bài toán, nếu giải được bài toán thì sẽ được thưởng 1 số tiền random(10K -> 100K), thế là 5 thanh niên này liền bắt tay vào giải bài toán để kiếm tiền chơi game. Nhưng bài toán quá khó, bạn có thể giải giúp 5 thanh niên này được không? \r\n\r\nCho 1 chuỗi kí tự $S$ chỉ gồm kí tự '(' và ')' và $m$ truy vấn, mỗi truy vấn là 2 số nguyên dương $l , r \\ (1 \\leq l \\leq r \\leq S.size())$.\r\n\r\n#### Lưu ý: $S.size()$ là số lượng kí tự của chuỗi $S$\r\n\r\n#### Yêu cầu: Hãy xác định dãy ngoặc đúng dài nhất trong đoạn $(l, r)$\r\n\r\n#### Input:\r\n + Dòng thứ nhất là chuỗi kí tự $S \\ (1 \\leq S.size() \\leq 10^6)$\r\n + Dòng thứ 2 là số nguyên dương $m$ là số lượng truy vấn $(1 \\leq m \\leq 10^5)$\r\n + $m$ dòng tiếp theo là 2 số nguyên dương $l, r \\ (1 \\leq l \\leq r \\leq S.size())$\r\n \r\n\r\n#### Output:\r\n + m dòng số nguyên dương , tương ứng với kết quả của đáp án\r\n\r\n\r\n#### Scoring:\r\n + Subtask $1$ ($43.33\\%$ số điểm): $1 \\leq S.size(), m \\leq 1000$ \r\n + Subtask $1$ ($56.67\\%$ số điểm): không có ràng buộc gì thêm\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        (((())((((()()((((((()((()(((((((((((()((\r\n        6\r\n        20 37\r\n        28 32\r\n        12 18\r\n        7 25\r\n        21 33\r\n        4 5\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        4\r\n        0\r\n        2\r\n        6\r\n        4\r\n        2\r\n        ```\r\n    ??? warning \"Note\"\r\n        Trong truy vấn thứ 1 ta có chuỗi `((()((()(((((((((`, ta thấy chuỗi có dãy ngoặc đúng dài nhất là `()()` . Vậy kết quả là 4","points":600.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}