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


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

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

Дана строка из скобок «(» и «)» и q запросов «l r». Для каждого запроса найдите наибольшую длину правильной скобочной последовательности, которую можно получить, вычеркнув часть символов подстроки sₗ…sᵣ.

Ввод. В первой строке n и q. Во второй — строка из n скобок. Затем q строк l r. 1 ≤ n, q ≤ 100000.

Вывод. Ответ на каждый запрос в отдельной строке.

Примеры

Ввод 1

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

Вывод 1

4
0

Комментарии

Еще нет ни одного комментария.