2021 ECNU XCPC 预备班 小测 #2

C. 括号

单点时限: 2.0 sec

内存限制: 512 MB

Rachel在学数据结构。Richard给她出了一道题,但她一下子想不出来,Richard又不愿意花时间提示她,于是可怜的她求助于你。

题目是这样的:给出一个由()字符组成的字符串。求出它最长的是合法括号序列的子串的长度,同时求出最长子串的个数。

如果一个括号序列插入若干+1后,可以得到一个正确的数学表达式,那么它被称为“合法”的。

例如,序列(())()()(()(()))是合法的,但)((()(()))(不是。

输入格式

一行包含一个非空字符串,由“ (”和“ )” 字符组成,长度不超过 $10^6$ 。

输出格式

输出最长合法括号序列的子串的长度,和最长子串的个数。
如果不存在这种子串,输出唯一的一行,包含 0 1

样例

Input
)((())))(()())
Output
6 2
Input
))(
Output
0 1