{"raw_statement":[{"iden":"statement","content":"圆给了你一个长度为 $n$ 的字符串 $S$，$S$ 仅由 ```(``` 和 ```)``` 构成。\n\n她会对其做 $m$ 次操作，操作有两种类型：\n\n1. ```1 l r```，她会翻转 $l$ 到 $r$ 的括号，即 ```(``` 变 ```)```，```)``` 变 ```(```。\n1. ```2 l r```，她想知道区间 $\\left[ l,r\\right]$ 中最长合法括号子序列的长度除以 $2$ 的答案。\n\n\n圆认为以下的括号序列是合法的：\n\n1. 空序列是一个合法序列。\n\n1. 如果 ```A``` 是一个合法序列，则 ```(A)```  也是一个合法序列。\n\n1. 如果 ```A``` 和 ```B``` 都是合法序列，则 ```AB``` 也是一个合法序列。\n\n圆认为，序列 $a$ 的子序列是满足 $1\\le i_1<i_2<···<i_k \\le n$ 的序列 $[a_{i_1},a_{i_2},...a_{i_k}]$。\n\n由于操作太多了，她算不过来，请你帮帮她吧。\n"},{"iden":"input","content":"第一行一个整数 $n$。\n\n第二行一个长度为 $n$ 的字符串 $S$，保证仅由 ```(``` 和 ```)``` 构成 。\n\n第三行一行一个整数 $m$。\n\n接下来 $m$ 行，每行三个数 $op$，$l$，$r$，对应上面的两种操作。"},{"iden":"output","content":"对于每一个 $op=2$ 的操作，输出一行一个整数，表示答案。"},{"iden":"note","content":"**【样例解释】**\n\n- 第一次截取的字符串是 ```()```，答案为 $1$。\n- 翻转后字符串变为 ```))(())```。\n- 第二次截取的字符串是 ```)(```，答案为 $0$。\n- 第三次截取的字符串是 ```())```，答案为 $1$。\n- 第四次截取的字符串是 ```(())```，答案为 $2$。\n\n**【数据范围】**\n\n- 对于 $10\\%$ 的数据，$1 \\leq n,m \\leq 500$；\n- 对于 $20\\%$ 的数据，$1 \\leq n,m \\leq 5000$；\n- 对于 $40\\%$ 的数据，$1 \\leq n,m \\leq 2\\times 10^5$；\n- 另有 $10\\%$ 的数据，满足 $op=2$ 且数据随机生成；\n- 另有 $15\\%$ 的数据，满足 $op=2$ 但不保证数据随机生成；\n\n对于所有数据，保证 $1\\le n \\le 5\\times 10^5$，$1\\le m \\le 5 \\times 10^5$，$1 \\le l \\le r \\le n$，$op \\in \\{1,2\\}$。数据有梯度。"}],"translated_statement":null,"sample_group":[["6\n(()())\n5\n2 2 3\n1 1 3\n2 2 3\n2 4 6\n2 3 6","1\n0\n1\n2"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}