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<cstdio>
#include<cstring>
#define N 1010000
char s[N];int n, t, m=1, a, c[N], l[N];
int main()
{	gets(s), n=strlen(s);	for (int i=0; i<n; i++)		{if (s[i]=='(') c[++t]=i;
		else if (t)
		{
			l[i]=i-c[t]+1+l[c[t]-1], t--;
			if (a==l[i]) m++; else
			if (a<l[i]) a=l[i], m=1;
		}}
	printf("%d %d\n",a,m);
}
	 		  	  	  	   						   					