Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «1» можно получить из нее корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет.
Однажды Васе попалась скобочная последовательность. Он решил удалить из нее некоторые скобки так, чтобы последовательность стала правильной. Какую наибольшую длину может иметь получившаяся правильная скобочная последовательность?
Выходные данные
Выведите длину наибольшей правильной скобочной подпоследовательности.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
(()))(
|
4
|
|
2
|
((()())
|
6
|