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>.
import sys


def front(ls):
    return ls[len(ls)-1];



def solve(string1):
    stack = []

    result = []
    n = len(string1)

    opening_pos = [-1]*n
    earliest_opening_pos = [-1]*n

    for i,val in enumerate(string1):

        if val == '(' or val == '{':
            stack.append(i)
        elif len(stack) != 0:
            fr_pos = front(stack)
            fr_val = string1[fr_pos]

            if fr_val=='(' and val == ')' or fr_val == '{' and val == '}':
                opening_pos[i] = fr_pos
                earliest_opening_pos[i] = fr_pos
                stack.pop()

                start_pos = opening_pos[i]-1

                if start_pos !=-1 and (string1[start_pos]=='}' or string1[start_pos]==')') and earliest_opening_pos[start_pos]!=-1:
                    earliest_opening_pos[i] = earliest_opening_pos[start_pos]
            else:
                stack.clear()

    longest_regular = 0
    longest_index =-1
    now_pos = n-1

    while now_pos>=0:
        e_pos = earliest_opening_pos[now_pos]
        if  e_pos != -1:
            if now_pos-e_pos+1 >= longest_regular:
                longest_index = now_pos
                longest_regular = now_pos-e_pos+1

        now_pos -= 1
    cnt =0
    now_pos =n-1
    while now_pos >= 0:
        e_pos = earliest_opening_pos[now_pos]
        if e_pos != -1:
            if now_pos - e_pos + 1 == longest_regular:
                cnt +=1

        now_pos -= 1

    if longest_index!=-1:
        print(-earliest_opening_pos[longest_index]+longest_index+1,cnt)
        # longest_regular = string1[earliest_opening_pos[longest_index]:longest_index+1]
    else:
        print("0 1")
        # longest_regular = ""
    #print(longest_regular)


def solveAll():
    txt= sys.stdin.read().strip()

    txt= txt.split('\n')

    for line in txt:
        solve(line)

solveAll()
