#CODEFORCESP7535. Longest Regular Bracket Sequence

    ID: 326 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>constructive algorithmsdata structuresdpgreedysortingsstrings*1900translated

Longest Regular Bracket Sequence

机翻

这是另一个涉及正则括号序列的问题。

我们应该提醒你,如果在一个括号序列中插入 "+" 和 "1" ,就可以得到一个正确的数学表达式,那么这个序列就被称为有规律的。例如,序列 "(())()" 、 "()" 和 "(()(()))" 是有规律的,而 ")(" 、 "(()" 和 "(()))(" 则不是。

你会得到一个由 "(" 和 ")" 字符组成的字符串。你要找出最长的子串,它是一个有规律的括号序列。你还要找出这种子串的数量。

输入文件的第一行包含一个非空字符串,由 "(" 和 ")" 字符组成。其长度不超过 106.

打印属于正括号序列的最长子串的长度,以及此类子串的数量。如果没有这样的子串,请写出唯一包含 "0 1" 的一行。

Description

This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical expression. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.

You are given a string of «(» and «)» characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".

Input

The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Output

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".

Samples

)((())))(()())
6 2
))(
0 1