## Algorithm

C. Longest Regular Bracket Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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".

Examples
input
Copy
`)((())))(()())`
output
Copy
`6 2`
input
Copy
`))(`
output
Copy
`0 1`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <vector>
#include <stack>

int main(){

std::string s; std::cin >> s;
std::vector<long> match(s.size(), -1);
std::vector<long> start(s.size(), -1);
std::stack<long> t;
long maxLen(0), count(1);
for(long p = 0; p < s.size(); p++){
if(s[p] == '('){t.push(p);}
else if((s[p] == ')') && (!t.empty())){
match[p] = t.top(); t.pop();
long cur = match[p];
long prev = (cur > 0) ? start[cur - 1] : -1;
start[p] = (prev >= 0) ? prev : cur;
long len = p - start[p] + 1;
if(len > maxLen){maxLen = len; count = 1;}
else if(len == maxLen){++count;}
}
}

std::cout << maxLen << " " << count << std::endl;

return 0;
}``````
Copy The Code &

Input

cmd
)((())))(()())

Output

cmd
6 2