13536번 - 괄호 부분 문자열 쿼리

괄호 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 괄호 문자열이다.
2. S가 괄호 문자열일 때, (S)도 괄호 문자열이다.
3. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다.
4. 모든 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다.

'('와 ')'로 이루어진 문자열 S = s₁s₂...s_N과 M개의 쿼리가 주어진다. 각각의 쿼리는 l_i와 r_i(1 ≤ l_i ≤ r_i ≤ n)로 이루어져 있다. 각각의 쿼리에 대해서 다음을 구해야 한다.

• S의 부분 문자열 s_li, s_li+1, ..., s_ri의 부분 수열 중에서 괄호 문자열이면서 가장 긴 것의 길이를 출력한다.

문자열 S = s₁s₂...s_N의 길이가 |x|인 부분 수열이란, 1 ≤ k₁ < k₂ < ..., K_|x| ≤ N을 만족하는 문자열 x = s_k1s_k2...s_k|x|를 의미한다.

첫째 줄에 문자열 S가 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

셋째 줄부터 M개의 줄에 쿼리 l_i와 r_i가 주어진다.

각각의 쿼리마다 정답을 출력한다.