N. Скобки на отрезке

Дана скобочная строка. Для каждого запроса $[l, r]$ выведите длину наибольшей правильной скобочной подпоследовательности подстроки $s_l \ldots s_r$.

Задача, где узел хранит «что осталось несопоставленным».

В первой строке — строка из символов ( и ) длиной $n$ ($1 \le n \le 2 \cdot 10^5$). Во второй — $m$ ($1 \le m \le 10^5$). В каждой из следующих $m$ строк — $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите на отдельной строке длину наибольшей правильной скобочной подпоследовательности.