这是处理常规括号序列的另一个问题。
我们应该提醒您,如果通过在其中插入“+”和“1”可以得到正确的数学表达式,则括号序列称为正则序列。例如,序列《(())()》、《()》和《(()(()))》是规则的,而《)(》、《(()》和《(()))(》则不是。
您将获得一个由 «(» 和 «)» 字符组成的字符串。你要找到它的最长子串,它是一个规则的括号序列。您还需要找到此类子串的数量。
输入
输入文件的第一行包含一个非空字符串,由 «(» 和 «)» 字符组成。它的长度不超过106。
输出
打印作为常规括号序列的最长子字符串的长度,以及此类子字符串的数量。如果没有这样的子字符串,则写入唯一包含“0 1”的行。
示例
输入 #1
)((())))(()())
输出 #1
6 2
输入 #2
))(
输出 #2
0 1