#D. Longest Regular Bracket Sequence

    远端评测题 2000ms 256MiB

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

7.7下午1点半作业

未认领
状态
已结束
题目
6
开始时间
2023-7-7 0:00
截止时间
2023-7-15 23:59
可延期
24 小时