EduBrick

O. Дерево из скобок

2000 мс · 256 МБ · всё или ничего

Правильная скобочная последовательность задаёт лес: каждая пара скобок — вершина, а то, что стоит внутри неё, — её дети.

Например, запись (()(())) задаёт одно дерево: у корня двое детей, у второго из них — ещё один ребёнок. Глубина такого дерева 3, листьев в нём 2 — это пары скобок, внутри которых пусто.

По записи найдите наибольшую глубину и количество листьев.

Глубина здесь — это ровно максимальная глубина рекурсии при разборе. Полезно понимать, что при длинной записи вида ((((...)))) рекурсия уходит глубоко, и об этом стоит помнить, а не узнавать из падения на тесте.

Формат ввода

Одна строка содержит правильную скобочную последовательность длиной от 2 до 2⋅1052 \cdot 10^5 символов.

Формат вывода

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

Примеры

ввод
(()(()))
вывод
3 2
ввод
()
вывод
1 1
Войдите, чтобы отправлять решения.