Задана последовательность из круглых и квадратных скобок. Над этой последовательностью можно произвести следующие операции:
- поменять вид скобки с открывающей на закрывающую и наоборот, не меняя форму скобки: то есть можно поменять '(' на ')' и ')' на '('; можно поменять '[' на ']' и ']' на '['. Эта операция стоит \(0\) бурлей.
- взять любую квадратную скобку и поменять на круглую, не меняя направление скобки: то есть можно поменять '[' на '(', но не '(' на '['; можно поменять ']' на ')', но не ')' на ']'. Эта операция стоит \(1\) бурль.
Операции можно производить в любом количестве в любом порядке.
Задана строка \(s\) длины \(n\) и \(q\) запросов вида «l r», где \(1 \le l < r \le n\). Для каждой подстроки \(s[l \dots r]\) найдите минимальную цену, которую нужно заплатить, чтобы сделать её правильной скобочной последовательностью. Гарантируется, что подстрока \(s[l \dots r]\) имеет чётную длину.
Запросы надо обрабатывать независимо, то есть изменения в строке, сделанные для ответа на запрос \(i\), не влияют на запросы \(j\) (\(j > i\)). Иными словами, при обработке запроса подстрока \(s[l \dots r]\) берётся из первоначальной заданной строки \(s\).
Правильная скобочная последовательность — это последовательность, которую можно построить по следующим правилам:
- пустая последовательность является правильной скобочной;
- если «s» — правильная скобочная последовательность, то последовательности «(s)» и «[s]» являются правильными скобочными;
- если «s» и «t» – правильные скобочные последовательности, то последовательность «st» (соединение этих последовательностей) является правильной скобочной.
Например, последовательности «», «(()[])», «[()()]()» и «(())()» являются правильными скобочными, в то время как «(», «[(])» и «)))» — нет.
Выходные данные
Для каждого запроса выведите в отдельной строке целое число \(x\) (\(x \ge 0\)) — минимальную цену, которую нужно заплатить, чтобы данная подстрока стала правильной скобочной последовательностью.
Примечание
Рассмотрим первый набор входных данных. Первый запрос описывает всю строку, её можно привести к следующей правильной скобочной последовательности: «([()])()[[]]». Форма скобок не изменена, поэтому стоимость изменения равна \(0\).
Второй запрос описывает подстроку «)[)()]». Её можно привести к последовательности «(()())», стоимость равна \(2\).
Третий запрос описывает подстроку «))[)». Её можно привести к последовательности «()()», стоимость равна \(1\).
Во втором наборе входных данных все подстроки состоят только из круглых скобок. Можно показать, что любую последовательность чётной длины из круглых скобок можно привести к правильной за \(0\) бурлей.
В третьем наборе входных данных единственный запрос описывает строку «[]», которая уже является правильной скобочной последовательностью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
([))[)()][]]
3
1 12
4 9
3 6
))))))
2
2 3
1 4
[]
1
1 2
|
0
2
1
0
0
0
|