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 10<sup class="upper-index">6</sup>.
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
ll N = 1e9 + 7;


void solution(string s){    
    int n = s.length();
    stack<int> st;
    vector<int> freq(n + 2, 0);
    vector<int> start(n + 2, -1);
    vector<int> ext(n + 2, -1);


    for (int i = 0; i < n; i++){    
        if (s[i] == ')' && st.empty()){
            start[i] = -1;
            continue;
        }
        if (s[i] == '('){
            st.push(i);
        }
        else{
            start[i] = st.top();
            ext[i] = st.top();
            st.pop();

            if (start[i] > 0){
                int left = start[i] - 1;
                if (s[left] == ')' && start[left] != -1){
                    ext[i] = min(start[left], ext[left]);
                }                
                ++freq[i - ext[i] + 1];
            }            
            else if (start[i] == 0){
                ++freq[i - start[i] + 1];
            }
        }
    }                
    
    for (int i = n; i >= 1; i--){
        if (freq[i] > 0){
            cout<<i<<" "<<freq[i]<<"\n";
            return;
        }
    }

    cout<<"0 1\n";
}

int main(int argc, char const *argv[]){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("inp.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    string s;
    cin>>s;

    solution(s);

    return 0;
}