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>.
from math import *
from collections import *

# hell = 10 ** 9 + 7
hell = 998244353


def precalculate(arr):
    n = len(arr)
    k = floor(log2(n)) + 1
    table = [[float('inf')] * k for _ in range(n)]
    for i in range(n):
        table[i][0] = arr[i]
    for l in range(1, k):
        for i in range(n):
            if i + (1 << (l - 1)) < n:
                table[i][l] = min(table[i][l - 1], table[i + (1 << (l - 1))][l - 1])
    return table


def getMin(table, left, right):
    # print(left, right)
    l = right - left + 1
    k = floor(log2(l))
    return min(table[left][k], table[right-(1 << k)+1][k])


def binary_search(table, indices, val):
    lo, hi = 0, len(indices)
    ans = -1
    while lo < hi:
        mid = (lo + hi) // 2
        if getMin(table, indices[0], indices[mid]) == val:
            ans = indices[mid] - indices[0]
            lo = mid + 1
        else:
            hi = mid
    return ans


def solve():
    s = input()
    n = len(s)
    mp = {'(': 1, ')': -1}
    prefix = [0] * (n + 1)
    val_to_indices = defaultdict(list)
    for i, c in enumerate(s):
        prefix[i+1] = prefix[i] + mp[c]
        val_to_indices[prefix[i+1]].append(i+1)
    # print(prefix)
    table = precalculate(prefix)
    # print(table)
    longest = 0
    done = set()
    count = defaultdict(int)
    for i in range(n+1):
        val = prefix[i]
        if val in done:
            continue
        indices = val_to_indices[val]
        done.add(val)
        # print(val, indices)
        here = binary_search(table, indices, val)
        # here = -1
        # for ind in indices:
        #     if getMin(table, i, ind) == val:
        #         here = ind - i
        longest = max(longest, here)
        count[here] += 1
    if longest:
        print(longest, count[longest])
    else:
        print("0 1")


def main():
    tc = 1
    # tc = int(input())
    for _ in range(tc):
        solve()


if __name__ == "__main__":
    main()
