Прошлым летом Feluda подарил Lalmohan-Babu правильную скобочную последовательность \(s\) длины \(2 n\).
Topshe скучал во время летних каникул, и поэтому решил нарисовать неориентированный граф из \(2 n\) вершин, используя правильную скобочную последовательность \(s\). Для каждых двух различных вершин \(i\) и \(j\) (\(1 \le i < j \le 2 n\)) Topshe рисует ребро между этими двумя вершинами тогда и только тогда, когда подотрезок \(s[i \ldots j]\) образует правильную скобочную последовательность.
Определите количество компонент связности в графе Topshe.
Смотрите определения подчёркнутых терминов в Примечании.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — количество компонент связности в графе Topshe.
Примечание
Объяснение примера:
В первом наборе входных данных, граф, построенный из скобочной последовательности (), является просто графом, содержащим вершины \(1\) и \(2\), соединёнными единственным ребром.
Во втором наборе входных данных, граф, построенный из скобочной последовательности ()(()) будет следующим (содержит две компоненты связности):
Определения подчёркнутых терминов:
- Последовательность скобок является правильной, если её можно превратить в корректное математическое выражение путём добавления символов \(+\) и \(1\). Например, последовательности (())(), () и (()(())) являются правильными, а )(, (() и (()))( не являются.
- Подотрезок \(s[l \ldots r]\) обозначает последовательность \([s_l, s_{l + 1}, \ldots, s_r]\).
- Компонента связности является множеством вершин \(X\) таким, что для каждых двух вершин из этого множества существует хотя бы один путь в графе, соединяющий эти вершины, но добавление любой другой вершины в \(X\) нарушает это правило.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
()
3
()(())
3
((()))
4
(())(())
|
1
2
3
3
|