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, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def sparse_table(a):
    table = []
    s0, l = a, 1
    table.append(s0)
    while 2 * l <= len(a):
        s = [min(s0[i], s0[i + l]) for i in range(len(s0) - l)]
        table.append(list(s))
        s0 = s
        l *= 2
    return table

def get_min(l, r, table):
    d = (r - l + 1).bit_length() - 1
    d = len(bin(r - l + 1)) - 3
    ans = min(table[d][l], table[d][r - pow2[d] + 1])
    return ans

s = list(input().rstrip())
x = [0]
for i in s:
    if not i & 1:
        x.append(x[-1] + 1)
    else:
        x.append(x[-1] - 1)
mi = min(x)
n = len(x)
for i in range(n):
    x[i] -= mi
m = max(x)
s = [0] * (m + 3)
for i in x:
    s[i + 2] += 1
for i in range(1, m + 3):
    s[i] += s[i - 1]
y = [0] * n
for i in range(n):
    j = x[i] + 1
    y[s[j]] = i
    s[j] += 1
pow2 = [1]
for _ in range(22):
    pow2.append(2 * pow2[-1])
table = sparse_table(x)
m, c = 0, 1
inf = pow(10, 9) + 1
l, r = y[0], y[0]
for i in range(n - 1):
    u, v = y[i], y[i + 1]
    xu, xv = x[u], x[v]
    if xu ^ xv or get_min(u, v, table) < xu:
        if m < r - l:
            m, c = r - l, 0
        if m == r - l:
            c += 1
        l, r = v, v
        continue
    r = v
if m < r - l:
    m, c = r - l, 0
if m == r - l:
    c += 1
if not m:
    c = 1
print(m, c)