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.

Input

The first line of the input file contains a non-empty string, consisting of «(» and «)» characters. Its length does not exceed 106.

Output

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".

Examples

Input

)((())))(()())


Output

6 2


Input

))(


Output

0 1

Difficulty: HARD
Tags: Constructive algorithms

String algorithms

Sorting

Greedy algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
string = input()
n = len(string)
stack = []
mapping = [0] * n
for (idx, char) in enumerate(string):
	if char == '(':
		stack.append(idx)
	elif char == ')' and stack:
		mapping[stack.pop()] = idx
i = 0
mx = 0
cnt = 1
tmp_max = 0
prev_join_idx = 0
while i < n:
	if mapping[i]:
		curr_len = mapping[i] - i + 1
		if i == prev_join_idx + 1:
			tmp_max += curr_len
		else:
			tmp_max = curr_len
		if tmp_max > mx:
			mx = tmp_max
			cnt = 1
		elif tmp_max == mx:
			cnt += 1
		prev_join_idx = mapping[i]
		i = mapping[i] + 1
	else:
		i += 1
print(mx, cnt)


def empty(l):
	return len(l) == 0

def longest_regular_bracket_sequence(str):
	st = []
	for ch in str:
		if ch == '(':
			st.append(('O', -1))
		else:
			valid_seq = False
			s = 0
			while not empty(st):
				(t, l) = st.pop()
				if t == 'O':
					valid_seq = True
					s += 2
					break
				elif t == 'R':
					s += l
				else:
					st.append(('C', -1))
					break
			if s != 0:
				st.append(('R', s))
			if not valid_seq:
				st.append(('C', -1))
	l = 0
	ml = 0
	cnt = 0
	while not empty(st):
		(t, l1) = st.pop()
		if t == 'R' and l1 != 0:
			l += l1
			if l == ml:
				cnt += 1
			elif l > ml:
				ml = l
				cnt = 1
		else:
			l = 0
	if ml == 0:
		cnt = 1
	return (ml, cnt)
s = input()
(ml, cnt) = longest_regular_bracket_sequence(s)
print(ml, cnt)


st = input()
b = []
for j in st:
	b.append(j)
n = len(b)
arr = []
dp = [0] * n
j = 0
while j < n:
	if b[j] == ')':
		if arr == []:
			pass
		elif arr[-1][0] == b[j]:
			pass
		else:
			p = arr.pop()
			dp[j] = j - p[1] + 1
			if p[1] - 1 >= 0 and b[p[1] - 1] == ')':
				dp[j] += dp[p[1] - 1]
	else:
		arr.append([b[j], j])
	j += 1
p = dp.count(max(dp))
if max(dp) == 0:
	print(0, 1)
else:
	print(max(dp), p)


s = input()
stack = []
high_length = 0
ss_count = 1
for i in range(0, len(s)):
	if s[i] == '(':
		stack.append(i)
	elif stack != [] and s[stack[-1]] == '(':
		stack.pop()
		if stack != []:
			length = i - stack[-1]
		else:
			length = i + 1
		if high_length < length:
			high_length = length
			ss_count = 1
		elif high_length == length:
			ss_count += 1
	else:
		stack.append(i)
print(high_length, ss_count)


(count, start, maxi) = (1, [-1], 0)
for (i, c) in enumerate(input()):
	if c == '(':
		start.append(i)
	elif len(start) > 1:
		start.pop()
		if maxi < i - start[-1]:
			(maxi, count) = (i - start[-1], 1)
		elif maxi == i - start[-1]:
			count += 1
	else:
		start[0] = i
print(maxi, count)


def main():
	string = input()
	correspondingOpen = [-2] * len(string)
	earliestOpen = [-2] * len(string)
	stack = []
	for i in range(len(string)):
		if string[i] == '(':
			stack.append(i)
		if string[i] == ')':
			if len(stack) == 0:
				correspondingOpen[i] = -1
				earliestOpen[i] = -1
			else:
				correspondingOpen[i] = stack.pop()
				if correspondingOpen[i] - 1 >= 0 and string[correspondingOpen[i] - 1] == ')' and (earliestOpen[correspondingOpen[i] - 1] != -1):
					earliestOpen[i] = earliestOpen[correspondingOpen[i] - 1]
					earliestOpen[correspondingOpen[i] - 1] = -2
				else:
					earliestOpen[i] = correspondingOpen[i]
	maxLength = 0
	countSequences = 0
	length = []
	i = len(string) - 1
	while i >= 0:
		if earliestOpen[i] >= 0:
			if i - earliestOpen[i] + 1 > maxLength:
				maxLength = i - earliestOpen[i] + 1
			length.append(i - earliestOpen[i] + 1)
			i = earliestOpen[i]
		i -= 1
	for i in range(len(length)):
		if maxLength == length[i]:
			countSequences += 1
	if countSequences == 0:
		countSequences = 1
	print(maxLength, countSequences)
main()


def magic(value=None):
	pairs = {}
	(maximum, count) = (0, 0)
	(num_of_opened, indices_of_opened) = (0, [])
	for (i, char) in enumerate(value or input()):
		if char == '(':
			indices_of_opened.append(i)
		elif indices_of_opened:
			o = indices_of_opened.pop()
			if o - 1 in pairs:
				start_of_previous = pairs[o - 1]
				pairs[i] = start_of_previous
				item_size = i - start_of_previous + 1
			else:
				item_size = i - o + 1
				pairs[i] = o
			if item_size > maximum:
				maximum = item_size
				count = 1
			elif item_size == maximum:
				count += 1
	if not maximum:
		return '0 1'
	return '%s %s' % (maximum, count)
print(magic())


import sys

def main():
	pattern = sys.stdin.readline().strip()
	max_length = 0
	substring_counter = 1
	stack = [-1]
	for (i, c) in enumerate(pattern):
		if c == '(':
			stack.append(i)
		else:
			stack.pop()
			if stack:
				if i - stack[-1] > max_length:
					max_length = i - stack[-1]
					substring_counter = 1
				elif i - stack[-1] == max_length:
					substring_counter += 1
			else:
				stack.append(i)
	sys.stdout.write(str(max_length) + ' ' + str(substring_counter) + '\n')
main()


s = input()
l = len(s)
lst = []
arr = []
for i in range(l):
	if s[i] == '(':
		lst.append(i)
	elif len(lst) != 0:
		j = lst[-1]
		del lst[-1]
		m = 2
		if len(arr) != 0:
			last = arr[-1]
			if last[0] < i and last[0] > j:
				m = m + last[-1]
				del arr[-1]
				if len(arr) != 0:
					last = arr[-1]
			if j - last[1] == 1:
				m = m + last[-1]
				del arr[-1]
		arr.append([j, i, m])
if len(arr) == 0:
	print(0, 1)
else:
	ct = 0
	mx = -1
	for i in arr:
		if i[-1] > mx:
			ct = 1
			mx = i[-1]
		elif i[-1] == mx:
			ct += 1
	print(mx, ct)


s = [-1]
l = 0
rep = 0
for (i, c) in enumerate(input()):
	if c == '(':
		s.append(i)
	elif len(s) > 1:
		s.pop()
		temp = i - s[-1]
		if temp > l:
			l = temp
			rep = 1
		elif temp == l:
			rep += 1
	else:
		s[0] = i
if l:
	print(l, rep)
else:
	print(0, 1)


def main():
	longest = 0
	count = 1
	unbalanced = list()
	push = unbalanced.append
	pop = unbalanced.pop
	head = -1
	for (cursor, paren) in enumerate(input()):
		if paren == '(':
			push(cursor)
		elif unbalanced:
			pop()
			span = cursor - (unbalanced[-1] if unbalanced else head)
			if span == longest:
				count += 1
			elif span > longest:
				longest = span
				count = 1
		else:
			head = cursor
	print(longest, count)
main()


s = input()
(w, c, b, l) = (0, 1, -1, [])
for i in range(len(s)):
	if s[i] == '(':
		l.append(i)
	elif l:
		l.pop()
		t = i - l[-1] if l else i - b
		if t > w:
			(w, c) = (t, 1)
		elif t == w:
			c += 1
	else:
		b = i
print(w, c)


from __future__ import print_function
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
from math import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
s = g()
stack = []
(ma, f) = (0, 1)
for ch in s:
	if ch == ')' and stack:
		if stack[-1] == '(':
			stack.pop()
			stack.append(2)
		elif stack[-1] == ')':
			stack.append(ch)
		elif len(stack) > 1:
			if stack[-2] == '(':
				v = stack.pop()
				stack.pop()
				stack.append(v + 2)
			else:
				stack.append(ch)
		else:
			stack.append(ch)
		if len(stack) > 1 and type(stack[-1]) == int:
			while len(stack) > 1 and type(stack[-2]) == int:
				stack[-2] += stack[-1]
				stack.pop()
	else:
		stack.append(ch)
for ch in stack:
	if type(ch) == int and ch >= ma:
		if ch > ma:
			ma = ch
			f = 1
		else:
			f += 1
print(ma, f)


s = input()
(ans, current) = (0, 0)
res = {}
stack = []
left = 0
for i in range(len(s)):
	if s[i] == '(':
		stack.append(-1)
	else:
		flag = False
		while len(stack) > 0 and stack[-1] != -2:
			if stack[-1] == -1:
				stack.pop()
				current += 2
				flag = True
				break
			else:
				current += stack[-1]
				stack.pop()
		stack.append(current)
		current = 0
		if not flag:
			stack.append(-2)
current = 0
while len(stack) > 0:
	if stack[-1] > 0:
		current += stack[-1]
	stack.pop()
	if len(stack) == 0 or stack[-1] < 0:
		if current in res:
			res[current] += 1
		else:
			res[current] = 1
		ans = max(ans, current)
		current = 0
if ans == 0:
	print('0 1')
else:
	print('%d %d' % (ans, res[ans]))


stack = [-1]
res = 0
nr_OfSubsequences = 1
signs = input()
for i in range(len(signs)):
	if signs[i] == '(':
		stack.append(i)
	elif len(stack) > 1:
		stack.pop()
		top = stack[-1]
		curr_lenght = i - top
		if curr_lenght > res:
			res = curr_lenght
			nr_OfSubsequences = 1
		elif res == curr_lenght:
			nr_OfSubsequences += 1
	else:
		stack[0] = i
print('%d %d' % (res, nr_OfSubsequences))


seq = input()
st = []
currentSize = 0
maxSize = 0
amount = 0
for c in seq:
	if c == ')' and len(st) > 0:
		currentSize += 2 + st.pop()
	else:
		if c == '(':
			st.append(currentSize)
		if currentSize > maxSize:
			maxSize = currentSize
			amount = 1
		elif currentSize == maxSize:
			amount += 1
		currentSize = 0
if currentSize > maxSize:
	maxSize = currentSize
	amount = 1
elif currentSize == maxSize:
	amount += 1
if maxSize == 0:
	amount = 1
print(maxSize, amount)


s = input().strip()
max_string = 0
total_max_strings = 0
stack = [None] * len(s)
arr = [None] * len(s)
top = -1
for (index, bracket) in enumerate(s):
	if bracket == '(':
		top += 1
		if arr[index - 1] != None:
			stack[top] = arr[index - 1]
		else:
			stack[top] = index
	elif top > -1:
		temp_len = index - stack[top] + 1
		if max_string < temp_len:
			max_string = temp_len
			total_max_strings = 1
		elif max_string == temp_len:
			total_max_strings += 1
		arr[index] = stack[top]
		top -= 1
print(max_string, total_max_strings or 1)


line = input().strip()
(d, c) = ([-1 for char in line], [-1 for char in line])
stack = []
for (i, char) in enumerate(line):
	if char == '(':
		stack.append(i)
	elif not stack:
		c[i] = -1
		d[i] = -1
	else:
		d[i] = stack.pop()
		if line[d[i] - 1] == ')' and c[d[i] - 1] != -1:
			c[i] = c[d[i] - 1]
		else:
			c[i] = d[i]
max_length = max((_ - c[_] if c[_] != -1 else -1 for _ in range(len(line))))
count_max = sum((1 if _ - c[_] == max_length and c[_] != -1 else 0 for _ in range(len(line))))
if max_length == -1:
	print('0 1')
else:
	print(max_length + 1, count_max)


import sys

def magic():
	(num_of_opened, indices_of_opened) = (0, [])
	for (i, char) in enumerate(input()):
		if char == '(':
			indices_of_opened.append(i)
		elif indices_of_opened:
			yield indices_of_opened.pop()
			yield i

def solve():
	(group, prev) = (0, 0)
	(maxgroup, maxgroupcount) = (0, 0)
	for index in sorted(magic()):
		sub = index - prev
		if sub == 1 or sub == index:
			group += 1
		elif group > 0:
			if maxgroup == group:
				maxgroupcount += 1
			if maxgroup < group:
				maxgroup = group
				maxgroupcount = 1
			group = 1
		prev = index
	if maxgroup < group:
		maxgroup = group
		maxgroupcount = 1
	elif maxgroup == group:
		maxgroupcount += 1
	return '%s %s' % (maxgroup, maxgroupcount)
print(solve())


def main():
	m = cnt = 1
	stack = [1]
	for c in input():
		if c == '(':
			stack.append(1)
		else:
			try:
				x = stack.pop() + stack.pop() + 1
				if m < x:
					m = x
					cnt = 1
				elif m == x:
					cnt += 1
				stack.append(x)
			except IndexError:
				stack = [1]
	m -= 1
	print(m, cnt if m else 1)
main()


import sys
import math
t = sys.stdin.read().split('\n')
if len(t) > 1:
	t.pop(-1)
t = t[0]
base = t
index = 0
current_length = 0
max_length = 0
count = 0
pares = 0
puedo_sumar = [False for x in t]
last_index = []
if True:
	o = 0
	index = 0
	for char in t:
		if char == '(':
			o += 1
			puedo_sumar[index] = False
			last_index += [index]
		elif char == ')':
			if o > 0:
				o -= 1
				puedo_sumar[index] = True
				puedo_sumar[last_index.pop(-1)] = True
		index += 1
count = 0
for value in puedo_sumar:
	if not value:
		current_length = 0
	else:
		current_length += 1
	if current_length > max_length:
		max_length = current_length
		count = 1
	elif current_length == max_length:
		count += 1
if max_length == 0:
	print('0 1')
else:
	print('{0} {1}'.format(max_length, count))


(inp, kol, max_len, pos) = (input(), 1, 0, [-1])
for i in range(len(inp)):
	if inp[i] == '(':
		pos.append(i)
	elif len(pos) > 1:
		pos.pop()
		x = i - pos[-1]
		if max_len < x:
			(max_len, kol) = (x, 1)
		elif max_len == x:
			kol += 1
	else:
		pos[0] = i
print(max_len, kol)


s = input()
N = len(s)
st = [-1]
(ml, cnt) = (0, 1)
for (i, c) in enumerate(s):
	if c == '(':
		st.append(i)
	elif len(st) > 1:
		st.pop(-1)
		ll = i - st[-1]
		if ll > ml:
			(ml, cnt) = (ll, 1)
		elif ll == ml:
			cnt += 1
	else:
		st[0] = i
print(ml, cnt)


from collections import Counter
s = input()
n = len(s)
d = []
c = dict()
for i in range(n):
	if s[i] == ')':
		if len(d) == 0:
			continue
		c[i] = i - d[-1] + 1 + c.get(d.pop() - 1, 0)
	else:
		d.append(i)
if len(c) == 0:
	print(0, 1)
else:
	res = Counter(c.values())
	m = max(res.keys())
	print(m, res[m])


import inspect

class Input:

	@classmethod
	def array_integer(cls):
		return MyList(map(int, input().split()))

	@classmethod
	def array_string(cls):
		return input().split()

	@classmethod
	def integer(cls):
		return int(input())

	@classmethod
	def float(cls):
		return float(input())

	@classmethod
	def string(cls):
		return input()

class Number:
	max = float('inf')
	min = -float('inf')

	@classmethod
	def is_digit(cls, character):
		return character in '0123456789'

class This:

	def __init__(self):
		self.max = self.min = self.sum = self.count = None
		self.set = set()
		self.map = dict()
		self.reset()

	def update_if_max(self, value):
		self.max = max(self.max, value)

	def update_if_min(self, value):
		self.min = min(self.min, value)

	def reset(self):
		self.min = Number.max
		self.max = Number.min
		self.sum = 0
		self.count = 0

class MyList(list):

	@property
	def length(self):
		return len(self)

	@property
	def is_empty(self):
		return not self

	@property
	def first(self):
		return self[0]

	@property
	def last(self):
		return self[-1]

	@property
	def is_sorted(self, key=lambda x: x):
		for i in range(len(self) - 1):
			if key(self[i]) > key(self[i + 1]):
				return False
		return True

	def push(self, element):
		return self.append(element)

	def for_each(self, callback):
		if not callable(callback):
			raise ValueError(f'Expected a function, got {callback} instead.')
		arg_count = len(inspect.getfullargspec(callback).args)
		for (i, item) in enumerate(self):
			arguments = []
			if arg_count >= 1:
				arguments.append(item)
			if arg_count >= 2:
				arguments.append(i)
			callback(*arguments)

	def map(self, callback):
		if not callable(callback):
			raise ValueError(f'Expected a function, got {callback} instead.')
		return MyList(map(callback, self))

	@classmethod
	def of(cls, size, value):
		if not isinstance(size, list):
			raise ValueError('Expected size to be a list of dimensions.')
		if len(size) == 0:
			raise ValueError('Size cannot be empty.')
		invalid_sizes_type = list(filter(lambda x: not isinstance(x, int), size))
		if len(invalid_sizes_type) > 0:
			raise ValueError('Sizes should be integers.')
		invalid_sizes_value = list(filter(lambda x: x <= 0, size))
		if len(invalid_sizes_value) > 0:
			raise ValueError('Sizes should be positive.')
		return MyList._of(size[::-1], value)

	@classmethod
	def _of(cls, size, value):
		if len(size) == 1:
			try:
				return MyList((value() for _ in range(size[0])))
			except TypeError:
				return MyList((value for _ in range(size[0])))
		else:
			count = size.pop()
			return MyList((MyList._of(size[:], value) for _ in range(count)))

	def copy(self):
		return MyList(list.copy(self))

	def __add__(self, other):
		return MyList(list.__add__(self, other))

	def __mul__(self, other):
		return MyList(list.__mul__(self, other))

class String(str):

	@property
	def length(self):
		return len(self)

	@property
	def is_empty(self):
		return not self

	@property
	def first(self):
		return self[0]

	@property
	def last(self):
		return self[-1]

	@property
	def is_sorted(self, key=lambda x: x):
		for i in range(len(self) - 1):
			if key(self[i]) > key(self[i + 1]):
				return False
		return True
	_alphabets = 'abcdefghijklmnopqrstuvwxyz'

	@classmethod
	def is_alphabet(cls, ch):
		return ch in String._alphabets

def solve():
	s = Input.string()
	dp = MyList.of([len(s)], 0)
	for (i, ch) in enumerate(s):
		if ch == ')':
			tween_length = 0 if i == 0 else dp[i - 1]
			match_index = i - tween_length - 1
			if match_index < 0 or s[match_index] != '(':
				continue
			prev_match_length = 0 if match_index - 1 < 0 else dp[match_index - 1]
			dp[i] += prev_match_length + 1 + tween_length + 1
	this = This()
	this.update_if_max(max(dp))
	if this.max == 0:
		print('0 1')
	else:
		print(f'{this.max} {dp.count(this.max)}')
solve()


from collections import *
s = input()
score = 0
stack = []
al = defaultdict(int)
val = 0
temp = []
saver = defaultdict(list)
saver[0].append(0)
for i in range(len(s)):
	if s[i] == ')':
		if score == 0:
			stack = []
			val = 0
			saver = defaultdict(list)
			saver[0].append(i + 1)
		else:
			stack.pop()
			score -= 1
			al[i - saver[score][-1] + 1] += 1
	else:
		stack.append('(')
		score += 1
		saver[score].append(i + 1)
	temp.append(val)
if len(al):
	print(max(al), al[max(al)])
else:
	print(0, 1)


def longestBracketSequence(S):
	stack = []
	pairIdxs = [-1 for _ in range(len(S))]
	extends = [-1 for _ in range(len(S))]
	frequence = [0 for _ in range(len(S) + 1)]
	l = 0
	for i in range(len(S)):
		c = S[i]
		if c == '(':
			stack.append(i)
		elif len(stack) > 0:
			idx = stack.pop()
			pairIdxs[i] = idx
			extends[i] = idx
			if idx > 0 and S[idx - 1] == ')' and (extends[idx - 1] >= 0):
				extends[i] = extends[idx - 1]
			j = i - extends[i] + 1
			frequence[j] += 1
			l = max(l, j)
	frequence[0] = 1
	print(l, frequence[l])
S = input()
longestBracketSequence(S)


s = input()
a = [-1] * len(s)
l = [0] * len(s)
q = []
for i in range(len(s)):
	if s[i] == '(':
		q.append(i)
	elif q:
		x = q.pop()
		a[i] = x
		l[i] += i - x + 1
		if x > 0:
			l[i] += l[x - 1]
(m, c) = (0, 1)
for i in range(len(s)):
	if l[i] > m:
		(m, c) = (l[i], 1)
	elif l[i] == m:
		c += 1
if m == 0:
	c = 1
print('%i %i' % (m, c))


s = input()
m = [-1] * len(s)
e = [-1] * len(s)
f = [0] * len(s)
stack = []
l = 0
for i in range(len(s)):
	if s[i] == '(':
		stack.append(i)
	elif len(stack) == 0:
		m[i] = -1
	else:
		p = stack.pop()
		m[i] = p
		if p == 0:
			e[i] = m[i]
		elif s[p - 1] == ')' and m[p - 1] >= 0:
			e[i] = e[p - 1]
		else:
			e[i] = m[i]
		if e[i] >= 0:
			c = i - e[i] + 1
			f[c - 1] += 1
for k in range(len(f)):
	if f[k] > 0:
		l = k
if l > 0:
	print(l + 1, f[l])
else:
	print(l, 1)


from collections import Counter as cr
st = input()
s = []
ans = [0, 0]
for i in st:
	if i == '(':
		ans.append(0)
		s.append(i)
	elif len(s) != 0:
		x = ans.pop()
		ans.append(x + 2)
		s.pop()
		x = ans.pop()
		y = ans.pop()
		ans.append(x + y)
	else:
		ans.append(0)
m = cr(ans)
c = max(ans)
if c == 0:
	print('0 1')
else:
	print(c, m[c])


s = input()
ans = dict()
stack = [-1]
res = 0
for i in range(len(s)):
	c = s[i]
	if c == ')' and stack[-1] != -1 and (s[stack[-1]] == '('):
		stack.pop()
		ans[i - stack[-1]] = ans.get(i - stack[-1], 0) + 1
		res = max(i - stack[-1], res)
	else:
		stack.append(i)
if res not in ans.keys():
	print('0 1')
else:
	print(' '.join([str(res), str(ans[res])]))


s = input().strip()
stack = []
valid = []
for k in range(len(s)):
	if s[k] == '(':
		stack.append(k)
	elif s[k] == ')':
		if not stack:
			pass
		else:
			popped = stack.pop()
			valid.append((popped, k))
num_substr = 0
maxlen = 0
if valid:
	prev = valid[-1]
for k in range(len(valid) - 2, -1, -1):
	if prev[0] < valid[k][0] and prev[1] > valid[k][1]:
		prev = prev
	elif prev[0] == valid[k][1] + 1:
		prev = (valid[k][0], prev[1])
	else:
		t = prev[1] - prev[0] + 1
		if t > maxlen:
			maxlen = t
			num_substr = 1
		elif t == maxlen:
			num_substr += 1
		prev = valid[k]
if valid:
	t = prev[1] - prev[0] + 1
	if t > maxlen:
		maxlen = t
		num_substr = 1
	elif t == maxlen:
		num_substr += 1
if num_substr == 0:
	num_substr = 1
print('{} {}'.format(maxlen, num_substr))


s = input()
s1 = 0
s2 = 0
ans = []
st = []
c = 0
for i in s:
	if i == '(':
		s1 += 1
		st.append(i)
	elif s1 > 0:
		c1 = 0
		while st[-1] != '(':
			k = st.pop()
			c1 += k
		c1 += 2
		st.pop()
		s1 -= 1
		st.append(c1)
	else:
		st.append(')')
ans = []
c = 0
kk = 1
for i in st:
	if i == ')' or i == '(':
		ans.append(c)
		c = 0
	else:
		c += i
		kk = 0
ans.append(c)
if kk == 1:
	print(0, 1)
else:
	print(max(ans), ans.count(max(ans)))


line = input()
all_pair = []
stack = []
for (i, ch) in enumerate(line):
	if ch == '(':
		stack.append(i)
	elif len(stack):
		left = stack.pop()
		all_pair.append((left, i))
all_pair.sort()
left = -2
right = -2
res = [0, 1]
for pair in all_pair:
	if pair[0] == right + 1:
		right = pair[1]
	elif right + 1 < pair[0]:
		(left, right) = pair
	else:
		continue
	length = right - left + 1
	if length > res[0]:
		res = [length, 1]
	elif length == res[0]:
		res[1] += 1
print(res[0], res[1])


s = input()
n = len(s)
ss = []
c = [-1 for j in range(n)]
d = [-1 for k in range(n)]
mlen = 0
cnt = 0
f = {0: 1}
for i in range(n):
	if s[i] == '(':
		ss.append(i)
	if ss != [] and s[i] == ')':
		c[i] = ss.pop()
		d[i] = c[i]
		if s[d[i] - 1] == ')' and c[d[i] - 1] != -1:
			c[i] = c[d[i] - 1]
for i in range(len(c)):
	if c[i] != -1:
		c[i] = i - c[i] + 1
mx = max(c)
if mx == -1:
	print(mlen, f[mlen])
else:
	print(mx, c.count(mx))


count = 1
stack = [-1]
string = input()
mx = 0
for i in range(len(string)):
	if string[i] == '(':
		stack.append(i)
	elif len(stack) > 1:
		stack.pop()
		n = i - stack[-1]
		if n > mx:
			mx = n
			count = 1
		elif n == mx:
			count += 1
	else:
		stack[0] = i
print(mx, count)


def main():
	longest = 0
	count = 1
	left = list()
	lead = 0
	push = left.append
	pop = left.pop
	for paren in input():
		if paren == '(':
			push(0)
		elif not left:
			lead = 0
		else:
			span = pop() + 2
			if left:
				span += pop()
				push(span)
			else:
				span += lead
				lead = span
			if span == longest:
				count += 1
			elif span > longest:
				longest = span
				count = 1
	print(longest, count)
main()


s = input()
n = len(s)
dp = []
stack = []
ans = []
for i in range(n):
	if s[i] == '(':
		dp.append(i)
		stack.append(i)
		ans.append(i)
	else:
		if not stack:
			dp.append(-1)
			ans.append(-1)
			continue
		dp.append(stack[-1])
		if dp[-1] - 1 >= 0 and s[dp[-1] - 1] == ')' and (ans[dp[-1] - 1] != -1):
			ans.append(ans[dp[-1] - 1])
		else:
			ans.append(dp[-1])
		stack.pop()
maxx = 0
count = 1
for i in range(len(ans)):
	if i == ans[i]:
		continue
	diff = i - ans[i] + 1
	if ans[i] != -1 and diff > maxx:
		maxx = diff
		count = 1
	elif ans[i] != -1 and diff == maxx:
		count += 1
print(maxx, count)


s = input().lstrip(')')
max_len = 0
num_max = 1
count = 0
start_pos = {}
for (i, c) in enumerate(s):
	if c == '(':
		count += 1
		if count not in start_pos:
			start_pos[count] = i
	else:
		count -= 1
		if count < 0:
			count = 0
			start_pos = {}
		if count + 2 in start_pos:
			del start_pos[count + 2]
		if count + 1 in start_pos:
			l = i - start_pos[count + 1] + 1
			if l > max_len:
				max_len = l
				num_max = 1
			elif l == max_len:
				num_max += 1
print(max_len, num_max)


s = input()
st = []
a = 0
b = 0
c = 0
m = 0
n = 0
for i in range(len(s)):
	if s[i] == '(':
		st.append(i)
	elif s[i] == ')':
		if st:
			st.pop()
			if st == []:
				if c != b:
					a = c
				b = i + 1
				c = i + 1
				if i - a + 1 > m:
					m = i - a + 1
					n = 1
				elif i - a + 1 == m:
					n += 1
		else:
			c = i + 1
z = len(s)
while st:
	c = st.pop()
	if z - c - 1 > m:
		m = z - c - 1
		n = 1
	elif z - c - 1 == m:
		n += 1
	z = c
if m == 0:
	n = 1
print(m, n)


(a, b) = (0, 1)
l = [-1]
for (i, c) in enumerate(input()):
	if c == '(':
		l.append(i)
	elif len(l) > 1:
		l.pop()
		minl = i - l[-1]
		if a < minl:
			(a, b) = (minl, 1)
		elif a == minl:
			b += 1
	else:
		l[0] = i
print(a, b)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
s = st()
n = len(s)
valid = [-1] * n
freq = [0] * (n + 1)
stack = []
for i in range(n):
	if s[i] == ')':
		if stack:
			last = stack.pop()
			if last - 1 >= 0 and valid[last - 1] != -1:
				last = valid[last - 1]
			valid[i] = last
			now = i - last + 1
			freq[now] += 1
	else:
		stack.append(i)
g = 0
for i in range(n, 0, -1):
	if freq[i] > 0:
		print(i, freq[i])
		g = 1
		break
if g == 0:
	print(0, 1)


s = ''.join(input().strip().split())
l = len(s)
stack = []
ans = 0
sub = 0
for i in range(l):
	if stack and stack[-1][0] == '(' and (s[i] == ')'):
		del stack[-1]
	else:
		stack.append((s[i], i))
stackl = len(stack)
if not stack:
	print(f'{l} 1')
elif l == stackl:
	print('0 1')
else:
	if stack[0][1] != 0:
		stack = [(0, -1)] + stack
	if stack[-1][1] != l - 1:
		stack = stack + [(0, l)]
	stackl = len(stack)
	for i in range(1, stackl):
		if ans == stack[i][1] - stack[i - 1][1] - 1:
			sub += 1
		elif ans < stack[i][1] - stack[i - 1][1] - 1:
			ans = stack[i][1] - stack[i - 1][1] - 1
			sub = 1
	print(ans, sub)


s = input()
n = len(s)
st = []
en = [0] * n
for i in range(n):
	if s[i] == '(':
		st.append(i)
	elif st:
		en[st.pop()] = i
ans = 0
mx = 0
cnt = 1
pen = 0
i = 0
while i < n:
	if en[i]:
		ta = en[i] - i + 1
		if i == pen + 1:
			ans += ta
		else:
			ans = ta
		if ans > mx:
			mx = ans
			cnt = 1
		elif ans == mx:
			cnt += 1
		pen = en[i]
		i = en[i] + 1
	else:
		i += 1
print(mx, cnt)


import sys
s = sys.stdin.readline().strip()
stack = []
dp = [0] * (len(s) + 1)
for i in range(len(s)):
	if s[i] == ')':
		if stack:
			begin = stack.pop()
			dp[i] = dp[begin - 1] + (i - begin + 1)
	else:
		stack.append(i)
mx = max(dp)
if mx == 0:
	print(0, 1)
else:
	print(mx, dp.count(mx))


from collections import deque

def main():
	st = deque()
	s = input()
	S = [-1 for i in range(len(s))]
	E = [-1 for i in range(len(s))]
	F = [0 for i in range(len(s) + 1)]
	F[0] = 1
	ma = 0
	for i in range(len(s)):
		if s[i] == '(':
			st.append(i)
		elif len(st) == 0:
			S[i] = E[i] = -1
		else:
			idx = st.pop()
			S[i] = E[i] = idx
			if idx > 0 and s[idx - 1] == ')' and (S[idx - 1] >= 0):
				E[i] = E[idx - 1]
			l = i - E[i] + 1
			F[l] += 1
			ma = max(ma, l)
	print(ma, F[ma])
main()


s = input()
n = len(s)
stack = []
dp = [0 for i in range(0, n)]
max_size = 0
max_cnt = 0
for i in range(0, n):
	c = s[i]
	if c == '(':
		stack.append(i)
	elif len(stack) > 0:
		prev = stack.pop()
		temp = dp[prev - 1] + i - prev + 1
		dp[i] = temp
		if temp > max_size:
			max_size = temp
			max_cnt = 1
		elif temp == max_size:
			max_cnt += 1
if max_size == 0:
	print('0 1')
else:
	print(max_size, max_cnt)


tmp = str(input())
local_start = None
local_max = 0
how_many = 1
lst = [-1]
for i in range(len(tmp)):
	if tmp[i] == '(':
		lst.append(i)
	elif len(lst) > 1:
		x = lst.pop()
		qq = i - lst[-1]
		if qq == local_max:
			how_many += 1
		elif qq >= local_max:
			local_max = qq
			how_many = 1
	else:
		lst[0] = i
print(local_max, how_many)


s = input()
st = []
p = len(s)
for i in range(p):
	if st != [] and s[i] == ')' and (s[st[-1]] == '('):
		st.pop()
	else:
		st.append(i)
if len(st) == p:
	print('0 1')
else:
	st.append(p)
	d = [0] * (1000000 + 7)
	k = -1
	ma = 0
	for i in st:
		if i - k - 1 >= ma:
			ma = i - k - 1
			d[i - k - 1] += 1
		k = i
	print(ma, d[ma])


line = input()
s = [-1]
max = 0
n_max = 0
i = 0
for a in line:
	if a == '(':
		s.append(i)
	elif len(s) > 1:
		e = s.pop()
		d = i - s[-1]
		if d > max:
			max = d
			n_max = 1
		elif d == max:
			n_max += 1
	else:
		s[0] = i
	i = i + 1
if max == 0:
	print(0, 1)
else:
	print(max, n_max)


s = input()
stack = [-1]
mx = 0
cnt = 1
for i in range(len(s)):
	elem = s[i]
	if elem == '(':
		stack.append(i)
	else:
		stack.append(i)
		if len(stack) >= 3:
			if s[stack[-2]] == '(' and s[stack[-1]] == ')':
				stack.pop()
				stack.pop()
				curr = i - stack[-1]
				if curr > mx:
					mx = curr
					cnt = 1
				elif curr == mx:
					cnt += 1
print(mx, cnt)


(m, b, s) = (0, 1, [-1])
for (i, c) in enumerate(input()):
	if c == '(':
		s.append(i)
	elif len(s) > 1:
		s.pop()
		n = i - s[-1]
		if m < n:
			(m, b) = (n, 1)
		elif m == n:
			b += 1
	else:
		s[0] = i
print(' '.join([str(m), str(b)]))


t = input()
a = [0] * (len(t) + 1)
m = n = k = 0
for i in range(len(t)):
	j = t[i]
	if j == '(':
		k += 1
		if k > 0:
			a[k] = i
	else:
		k -= 1
		if k < 0:
			k = 0
			a[k] = i + 1
			w = 0
		elif k == 0:
			w = i - a[k] + 1
		else:
			w = i - a[k]
		if w > m:
			m = w
			n = 1
		elif w == m:
			n += 1
if m == 0:
	n = 1
print(m, n)


s = input()
st = list()
c = 0
x = 0
max = 0
st.append(-1)
for i in range(len(s)):
	if s[i] == '(':
		st.append(i)
	else:
		st.pop()
		if st:
			c = i - st[-1]
			if c > max:
				max = c
				x = 1
			elif c >= 1 and c == max:
				x += 1
		else:
			st.append(i)
if x >= 1:
	print(str(max) + ' ' + str(x))
else:
	print('0 1')


from sys import stdin, stdout
input = stdin.readline
s = input()
s = s[:-1]
n = len(s)
substring = [None for i in range(n)]
ending = [None for i in range(n)]
frequency = [0 for i in range(n + 1)]
stack = []
for (index, character) in enumerate(s):
	if character == '(':
		stack.append(index)
		continue
	if len(stack) == 0:
		continue
	ind = stack.pop()
	substring[index] = ind
	ending[index] = ind
	if ind > 0:
		ind -= 1
		if s[ind] == ')' and substring[ind] != None:
			ending[index] = ending[ind]
	if ending[index] != None:
		frequency[index - ending[index] + 1] += 1
(mx, cnt) = (0, 1)
for (index, freq) in enumerate(frequency):
	if freq > 0 and index > mx:
		(mx, cnt) = (index, freq)
print(mx, cnt)


from collections import defaultdict
import bisect
from itertools import accumulate
import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
s = input()
(stack, c, l, ll) = ([-1], 1, 0, 0)
for i in range(len(s)):
	if s[i] == '(':
		stack.append(i)
	else:
		stack.pop()
		if stack:
			k = stack[-1]
			if i - stack[-1] > ll:
				ll = i - stack[-1]
				c = 1
			elif i - stack[-1] == ll:
				c += 1
		else:
			stack.append(i)
print(ll, c)


s = str(input())

def solve(s, k):
	stack = []
	n = len(s)
	ans = [0]
	prev = 0
	for i in range(n):
		if s[i] == k:
			if stack:
				val = i + 1 - stack.pop()
				if not stack:
					prev += val
					ans.append(prev)
				else:
					ans.append(val)
			else:
				prev = 0
		else:
			stack.append(i)
	Max = max(ans)
	return [Max, ans.count(Max)]
(a, b) = solve(s, ')')
(c, d) = solve(s[::-1], '(')
if a > c:
	print(a, b)
elif a == c:
	print(a, max(b, d))
else:
	print(c, d)


exp = input()
n = len(exp)
Pair = [-30] * (n + 1)
S = [0] * n
cnt = -1
for i in range(n):
	if exp[i] == '(':
		cnt += 1
		S[cnt] = i
	elif exp[i] == ')':
		if cnt >= 0:
			Pair[S[cnt]] = i
			cnt -= 1
Max = 0
cnt = 1
last = -100
i = 0
while i < n:
	tmp = Pair[i] - i + 1
	if tmp > 0:
		i += tmp
		tmp = max(tmp, tmp + last)
	else:
		i += 1
	last = tmp
	if tmp > Max:
		Max = tmp
		cnt = 1
	elif tmp == Max:
		cnt += 1
print(Max, cnt)


(ins, maxlen, count, stack) = (input(), 0, 1, [-1])
for (i, c) in enumerate(ins):
	if c == '(':
		stack.append(i)
	elif len(stack) > 1:
		stack.pop()
		x = i - stack[-1]
		if maxlen < x:
			(maxlen, count) = (x, 1)
		elif maxlen == x:
			count += 1
	else:
		stack[0] = i
print(maxlen, count)


import sys
from time import time
from typing import Tuple
(OPEN, CLOSE) = ('(', ')')

def magic(data: Tuple):
	(num_of_opened, i) = (0, 0)
	num_of_chars = len(data)
	indices_of_opened = []
	while i < num_of_chars:
		char = data[i]
		if char == OPEN:
			indices_of_opened.append(i)
			num_of_opened += 1
		elif num_of_opened > 0 and char == CLOSE:
			num_of_opened -= 1
			yield indices_of_opened.pop()
			yield i
		i += 1

def solve(string):
	(group, prev) = (0, 0)
	(maxgroup, maxgroupcount) = (0, 0)
	for index in sorted(magic(tuple(string))):
		sub = index - prev
		if sub == 1 or sub == index:
			group += 1
		elif group > 0:
			if maxgroup == group:
				maxgroupcount += 1
			if maxgroup < group:
				maxgroup = group
				maxgroupcount = 1
			group = 1
		prev = index
	if maxgroup < group:
		maxgroup = group
		maxgroupcount = 1
	elif maxgroup == group:
		maxgroupcount += 1
	return '%s %s' % (maxgroup, maxgroupcount)
print(solve(sys.stdin.readline()))


def checker(string):
	n = len(string)
	stack = [-1]
	max_value = 0
	max_count = 1
	for i in range(n):
		if string[i] == '(':
			stack.append(i)
		elif len(stack) > 1:
			stack.pop()
			length = i - stack[-1]
			if length == max_value:
				max_count += 1
			elif length >= max_value:
				max_value = length
				max_count = 1
		else:
			stack[0] = i
	return (max_value, max_count)
s = input()
(max_value, max_count) = checker(s)
print(max_value, max_count)


E = [0] * 1000001
S = [0] * 1000001
f = [0] * 1000001
s = input()
stack = []
n = len(s)
mx = 0
for i in range(n):
	if s[i] == '(':
		stack.append(i)
	elif stack == []:
		S[i] = -1
		E[i] = -1
	else:
		j = stack.pop()
		S[i] = E[i] = j
		if j > 0 and s[j - 1] == ')' and (S[j - 1] >= 0):
			E[i] = E[j - 1]
		l = i - E[i] + 1
		f[l] = f[l] + 1
		mx = max(mx, l)
f[0] = 1
print(mx, end=' ')
print(f[mx])


s = input()
a = []
n = len(s)
c = [-1 for i in range(n)]
d = [-1 for i in range(n)]
for i in range(len(s)):
	if s[i] == '(':
		a.append(i)
	elif len(a) > 0:
		d[i] = a[-1]
		c[i] = d[i]
		a.pop()
		if d[i] - 1 > -1:
			if c[d[i] - 1] != -1:
				c[i] = c[d[i] - 1]
length = 0
ans = 0
for i in range(n):
	if c[i] is not -1:
		if length < i - c[i] + 1:
			length = i - c[i] + 1
			ans = 1
		elif length == i - c[i] + 1:
			ans += 1
if length == 0:
	print(0, 1)
else:
	print(length, ans)


n = input()
(s, a, b, c) = ([], 0, -1, 1)
for i in range(len(n)):
	if n[i] == '(':
		s.append(i)
	elif s:
		s.pop()
		t = i - s[-1] if s else i - b
		if t > a:
			(a, c) = (t, 1)
		elif t == a:
			c += 1
	else:
		b = i
print(a, c)


import sys
input = lambda : sys.stdin.readline().strip()
s = input()
stack = []
m = 0
ans = 1
xx = -1
for i in range(len(s)):
	if s[i] == '(':
		stack.append(i)
	elif len(stack) > 0:
		stack.pop()
		optimal = i - stack[-1] if len(stack) > 0 else i - xx
		if optimal >= m:
			if optimal > m:
				(m, ans) = (optimal, 1)
			else:
				ans += 1
	else:
		xx = i
print(m, ans)


s = input()
n = len(s)
d = {}
d[0] = -1
d[1] = 0
v = 1
st = []
m = 0
c = 1
st.append(s[0])
for i in range(1, n):
	if s[i] == ')' and v > 0 and (st[v - 1] == '('):
		st.pop()
		v -= 1
		if m == i - d[v]:
			c += 1
		elif m < i - d[v]:
			m = i - d[v]
			c = 1
	else:
		v += 1
		d[v] = i
		st.append(s[i])
print(m, c)


string = input()
close_ = open_ = max_len = 0
counter = 1
dp = [True] * len(string)
for idx in range(len(string)):
	if string[idx] == '(':
		open_ += 1
	else:
		close_ += 1
	if open_ == close_:
		len_ = 2 * open_
		if len_ > max_len:
			(max_len, dp[idx - len_ + 1], counter) = (len_, False, 1)
		elif len_ == max_len:
			dp[idx - len_ + 1] = False
			counter += 1
	elif close_ > open_:
		close_ = open_ = 0
close_ = open_ = 0
for idx in range(len(string))[::-1]:
	if string[idx] == '(':
		open_ += 1
	else:
		close_ += 1
	if open_ == close_:
		len_ = 2 * open_
		if len_ > max_len:
			(max_len, counter) = (len_, 1)
		elif len_ == max_len:
			if dp[idx]:
				counter += 1
	elif open_ > close_:
		close_ = open_ = 0
print(max_len, counter)


s = input()
(stack, c, l, ll) = ([-1], 1, 0, 0)
for i in range(len(s)):
	if s[i] == '(':
		stack.append(i)
	else:
		stack.pop()
		if stack:
			k = stack[-1]
			if i - stack[-1] > ll:
				ll = i - stack[-1]
				c = 1
			elif i - stack[-1] == ll:
				c += 1
		else:
			stack.append(i)
print(ll, c)


def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def msi():
	return map(str, input().split())

def li():
	return list(mi())
s = si()
dp = [0] * (len(s) + 1)
ocnt = 0
for i in range(len(s)):
	if s[i] == '(':
		ocnt += 1
	elif ocnt > 0:
		ocnt -= 1
		if s[i - 1] == ')':
			dp[i] = dp[i - 1] + 2
		elif i > 1:
			if s[i - 2] == ')':
				dp[i] = 2 + dp[i - 2]
			else:
				dp[i] = 2
		else:
			dp[i] = 2
		dp[i] = dp[i] + dp[i - dp[i]]
if max(dp) == 0:
	print(0, 1)
else:
	print(max(dp), dp.count(max(dp)))


x = input()
ex = [-1] * len(x)
m = 0
f = [0] * len(x)
ans1 = -1
s = []
for (index, i) in enumerate(x):
	if i == '(':
		s.append(index)
	elif len(s) > 0:
		p = s.pop()
		ex[index] = p
		if p > 0 and ex[p - 1] > -1:
			ex[index] = ex[p - 1]
		f[index - ex[index]] += 1
		ans1 = max(ans1, index - ex[index])
print(ans1 + 1, max(1, f[ans1]))


seq = input()
longest = 0
total = 0
st = [-1]
for i in range(len(seq)):
	ch = seq[i]
	if ch == ')':
		if len(st) > 0 and st[-1] >= 0 and (seq[st[-1]] == '('):
			st.pop()
		else:
			st.append(i)
	else:
		st.append(i)
st.append(len(seq))
if len(st) > 0:
	longest = st[0]
m = {}
for i in range(1, len(st)):
	if st[i - 1] + 1 != st[i]:
		length = st[i] - st[i - 1] - 1
		longest = max(longest, length)
		if length not in m:
			m[length] = 1
		else:
			m[length] += 1
if longest > 0:
	print(longest, m[longest])
else:
	print(0, 1)


s = input()
n = len(s)
l1 = [-1] * n
l2 = [-1] * n
l3 = [0] * (n + 1)
l = []
for i in range(n):
	if s[i] == '(':
		l.append(i)
	elif len(l):
		a = l[-1]
		l.pop()
		l1[i] = i
		if a != 0:
			if l2[a - 1] != -1:
				l2[i] = l2[a - 1]
			else:
				l2[i] = a
		else:
			l2[i] = 0
		l3[l1[i] - l2[i] + 1] += 1
(ans1, ans2) = (0, 1)
for i in range(n, -1, -1):
	if l3[i] != 0:
		ans1 = i
		ans2 = l3[i]
		break
print(ans1, ans2)


string = input()
st = list()
mx = occ = 0
scores = [1] * len(string) + [0]
for (idx, c) in enumerate(string):
	if len(st) == 0:
		st.append(idx)
	elif string[st[-1]] == '(' and c == ')':
		popped = st.pop()
		scores[idx + 1] += scores[idx] + scores[popped]
		combined = scores[idx] + scores[popped]
		if combined > mx:
			mx = combined
			occ = 1
		elif combined == mx:
			occ += 1
	else:
		st.append(idx)
if mx == 0:
	print(mx, 1)
else:
	print(mx, occ)


s = input()
st = []
ans = []
for (i, c) in enumerate(s):
	if c == '(':
		st.append(i)
	elif st:
		q = st.pop()
		cur = [q, i]
		while True:
			if ans:
				(x, y) = ans[-1]
				if x == cur[0] + 1 and y == cur[1] - 1:
					ans.pop()
				elif y == cur[0] - 1:
					ans.pop()
					cur[0] = x
				else:
					break
			else:
				break
		ans.append(cur)
mx = 0
mc = 1
for (x, y) in ans:
	if y - x + 1 > mx:
		mx = y - x + 1
		mc = 1
	elif y - x + 1 == mx:
		mc += 1
print(mx, mc)


def get_result(string):
	brackets = [0] * len(string)
	stack = []
	for (i, s) in enumerate(string):
		if s == '(':
			stack.append(i)
		elif stack:
			brackets[stack.pop()] = 1
			brackets[i] = 1
	max_len = 0
	count = 0
	cur_chain = 0
	for (i, bracket) in enumerate(brackets):
		if not bracket and cur_chain:
			if cur_chain > max_len:
				max_len = cur_chain
				count = 1
			elif cur_chain == max_len:
				count += 1
			cur_chain = 0
		else:
			cur_chain += bracket
	if cur_chain > max_len:
		return (cur_chain, 1)
	elif cur_chain == max_len:
		count += 1
	return (max_len, count)
import sys
line = next(sys.stdin).strip()
(max_len, count) = get_result(line)[:2]
print(f'{max_len} {count or 1}')


import sys
inp = sys.stdin.readlines()
inp1 = inp[0]
leninp1 = len(inp1) - 1
stack = [0] * (leninp1 + 1)
top = -1
repetetion = [0] * (leninp1 + 1)
maxCount = 0
stack[0] = -1
top += 1
for i in range(leninp1):
	if inp1[i] == '(':
		stack[top + 1] = i
		top += 1
	else:
		top -= 1
		if top == -1:
			stack[top + 1] = i
			top += 1
		else:
			maxCount = max(maxCount, i - stack[top])
			repetetion[i - stack[top]] += 1
if maxCount != 0:
	print(str(maxCount) + ' ' + str(repetetion[maxCount]))
else:
	print('0 1')


s = input()
n = len(s)
stack = []
valid = [-1 for i in range(n)]
freq = [0] * (n + 1)
extension = [-1 for i in range(n)]
for i in range(n):
	if s[i] == '(':
		stack.append(i)
	elif stack:
		index = stack.pop()
		valid[i] = index
		extension[i] = index
		if index - 1 > 0 and s[index - 1] == ')' and (valid[index - 1] != -1):
			extension[i] = extension[index - 1]
		length = i - extension[i] + 1
		freq[length] += 1
ans = 0
for i in range(n, -1, -1):
	if freq[i]:
		print(i, freq[i])
		break
else:
	print(0, 1)


from collections import deque
s = input()
stack = deque()
l = len(s)
stack.append(-1)
count = res = 0
for i in range(l):
	if s[i] == '(':
		stack.append(i)
	else:
		stack.pop()
		if stack:
			if i - stack[-1] > res:
				count = 1
			elif i - stack[-1] == res:
				count += 1
			res = max(res, i - stack[-1])
		else:
			stack.append(i)
if res:
	print(res, count)
else:
	print(0, 1)


(z, zz) = (input, lambda : list(map(int, z().split())))
zzz = lambda : [int(i) for i in stdin.readline().split()]
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))
from string import *
from collections import *
from queue import *
from sys import *
from collections import *
from math import *
from heapq import *
from itertools import *
from bisect import *
from collections import Counter as cc
from math import factorial as f
from bisect import bisect as bs
from bisect import bisect_left as bsl
from itertools import accumulate as ac

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def prime(x):
	p = ceil(x ** 0.5) + 1
	for i in range(2, p):
		if x % i == 0 and x != 2 or x == 0:
			return 0
	return 1

def dfs(u, visit, graph):
	visit[u] = True
	for i in graph[u]:
		if not visit[i]:
			dfs(i, visit, graph)
st = [-1]
(mx, cnt) = (0, 0)
for (i, j) in enumerate(z()):
	if j == '(':
		st.append(i)
	elif len(st) > 1:
		st.pop()
		temp = i - st[-1]
		if temp > mx:
			mx = temp
			cnt = 1
		elif temp == mx:
			cnt += 1
	else:
		st[0] = i
if mx:
	print(mx, cnt)
else:
	print(0, 1)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(s):
	c = 0
	(ans, tmp, count) = (0, 0, 0)
	for (i, v) in enumerate(s):
		if v == '(':
			c += 1
		else:
			c -= 1
			if c >= 0:
				tmp += 1
			else:
				if tmp > ans:
					ans = tmp
					count = 1
				elif tmp > 0 and tmp == ans:
					count += 1
				tmp = 0
				c = 0
	if c == 0:
		if tmp > ans:
			ans = tmp
			count = 1
		elif tmp > 0 and tmp == ans:
			count += 1
	return (ans * 2, max(count, 1))
s = input()
(a, b) = solve(s)
(c, d) = solve(['(' if v == ')' else ')' for v in s[::-1]])
if a > c or (a == c and b >= d):
	print('{} {}'.format(a, b))
else:
	print('{} {}'.format(c, d))


from collections import deque

def solve(st):
	stack = deque()
	mx = 0
	for i in range(len(st)):
		if st[i] == '(':
			stack.append(i)
		elif len(stack) == 0:
			S[i] = -1
			E[i] = -1
		else:
			ri = stack.pop()
			S[i] = ri
			E[i] = ri
			if ri > 0 and st[ri - 1] == ')' and (S[ri - 1] >= 0):
				E[i] = E[ri - 1]
			l = i - E[i] + 1
			F[l] += 1
			mx = max(mx, l)
	F[0] = 1
	print(mx, F[mx])
max_l = 1000001
F = [0 for i in range(max_l)]
S = [0 for i in range(max_l)]
E = [0 for i in range(max_l)]
s = input()
solve(s)


import sys

class Stack:

	def __init__(self):
		self.stack = list()
		self.len = 0

	def is_empty(self):
		return self.len == 0

	def top(self):
		if self.is_empty():
			return None
		return self.stack[-1]

	def push(self, elt):
		self.stack.append(elt)
		self.len += 1

	def pop(self):
		if self.is_empty():
			return None
		self.len -= 1
		return self.stack.pop(-1)

	def clear(self):
		self.stack = list()
		self.len = 0

	def replace(self, pos, elt):
		self.stack[pos] = elt

	def __repr__(self):
		return f'Stack: {self.stack}'
CLOSE = ')'
OPEN = '('

def max_regular(s):
	(max_len, num_maxes, reg_len) = (0, 0, None)
	good_start = -1
	stack = Stack()
	for (i, p) in enumerate(s):
		if p == OPEN:
			stack.push(i)
		elif p == CLOSE:
			if stack.is_empty():
				good_start = i
			else:
				stack.pop()
				if stack.is_empty():
					reg_len = i - good_start
				else:
					reg_len = i - stack.top()
				if max_len < reg_len:
					(max_len, num_maxes) = (reg_len, 1)
				elif max_len == reg_len:
					num_maxes += 1
	return (max_len, num_maxes)
seq = input().strip()
(max_len, num_maxes) = max_regular(seq)
if max_len == 0:
	num_maxes = 1
print(f'{max_len} {num_maxes}')


s = input()
n = len(s)
sa = [-1] * n
f = [0] * (n + 1)
ex = [-1] * n
arr = []
for i in range(n):
	if s[i] == '(':
		arr.append(i)
	elif len(arr) != 0:
		p = arr.pop()
		sa[i] = p
		ex[i] = p
		if s[p - 1] == ')' and sa[p - 1] != -1:
			ex[i] = ex[p - 1]
		d = i - ex[i] + 1
		f[d] += 1
flag = False
for i in range(len(f) - 1, -1, -1):
	if f[i] != 0:
		print(i, f[i])
		flag = True
		break
if flag == False:
	print(0, 1)


string = input()
index = [-1]
count = 1
ma = 0
for i in range(len(string)):
	if string[i] == '(':
		index.append(i)
	elif len(index) > 1:
		index.pop()
		n = i - index[-1]
		if ma < n:
			ma = n
			count = 1
		elif ma == n:
			count += 1
	else:
		index[0] = i
print(str(ma), '', str(count))


input_str = input().strip()
stack = []
maxlen = 0
subs_count = 0
count = 0
open_bracks = 0
for i in input_str:
	if i == '(':
		stack.append('(')
		open_bracks += 1
	elif stack != [] and open_bracks > 0:
		open_bracks -= 1
		temp = 2
		if stack[-1] != '(':
			temp += int(stack.pop())
		if stack != [] and stack[-1] == '(':
			stack.pop()
			if stack != [] and stack[-1] not in ['(', '\n']:
				stack.append(temp + int(stack.pop()))
			else:
				stack.append(temp)
	else:
		stack.append('\n')
while stack != []:
	val = stack.pop()
	if val not in ['(', '\n']:
		val = int(val)
		if maxlen < val:
			maxlen = val
			count = 1
		elif maxlen == val:
			count += 1
if maxlen == 0:
	count = 1
print(maxlen, count)


import sys, os, io
from sys import stdin
import math
from collections import defaultdict
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')
s = si()
n = len(s)
dp = [0] * (n + 1)
for i in range(1, n + 1):
	if i > 1 and s[i - 1] == ')':
		if s[i - 2] == '(':
			dp[i] = dp[i - 2] + 2
		else:
			x = dp[i - 1]
			y = i - x - 1
			if y > 0 and s[y - 1] == '(':
				dp[i] = dp[i - 1] + 2 + dp[y - 1]
if max(dp) == 0:
	print(0, 1)
	exit()
print(max(dp), dp.count(max(dp)))


from collections import defaultdict
(t, r, p) = (input(), {'(': 1, ')': -1}, defaultdict(int))
(l, k, s, x) = (0, 1, 0, -1)
for (i, c) in enumerate(t, 1):
	y = r[c]
	if x < 0:
		if p[s]:
			d = i - p[s]
			if d >= l:
				if d > l:
					(l, k) = (d, 1)
				else:
					k += 1
			if y < 0:
				p[s] = 0
		elif y > 0:
			p[s] = i
	elif y > 0:
		p[s] = i
	x = y
	s += y
if x < 0 and p[s]:
	d = len(t) + 1 - p[s]
	if d >= l:
		if d > l:
			(l, k) = (d, 1)
		else:
			k += 1
print(l, k)


s = input()
arr = [-1]
longest_len = 0
count = 1
for (j, k) in enumerate(s):
	if k == '(':
		arr.append(j)
	elif len(arr) > 1:
		arr.pop()
		mini = j - arr[-1]
		if longest_len < mini:
			(longest_len, count) = (mini, 1)
		elif longest_len == mini:
			count += 1
	else:
		arr[0] = j
print(longest_len, count)


line = input()
s = [-1]
max_len = 0
max_num = 1
l = len(line)
for i in range(l):
	if line[i] == '(':
		s.append(i)
	elif len(s) > 1:
		s.pop()
		n = i - s[-1]
		if max_len < n:
			(max_len, max_num) = (n, 1)
		elif max_len == n:
			max_num += 1
	else:
		s[0] = i
print(str(max_len) + ' ' + str(max_num))


inputs = input()
c = [-1] * len(inputs)
stack = []
(ans, count) = (0, 1)
for (index, item) in enumerate(inputs):
	if item == '(':
		stack.append(index)
	elif stack:
		x = stack.pop()
		if x:
			c[index] = x if c[x - 1] == -1 else c[x - 1]
		else:
			c[index] = x
		tmp = index - c[index] + 1
		if ans < tmp:
			(ans, count) = (tmp, 1)
		elif ans == tmp:
			count += 1
print(ans, count)


s = input()
a = []
for i in range(len(s)):
	if len(a) != 0 and s[a[-1]] == '(' and (s[i] == ')'):
		a.pop()
	else:
		a.append(i)
if len(a) == len(s):
	print(0, 1)
elif len(a) == 0:
	print(len(s), 1)
else:
	b = [a[0] - 0]
	for i in range(len(a) - 1):
		b.append(a[i + 1] - a[i] - 1)
	b.append(len(s) - a[-1] - 1)
	m = max(b)
	print(m, b.count(m))


s = input()
stack = [-1]
max_count = 1
max_size = 0
for (i, w) in enumerate(s):
	if w == '(':
		stack.append(i)
	elif len(stack) > 1:
		stack.pop()
		t = i - stack[-1]
		if max_size < t:
			max_size = t
			max_count = 1
		elif max_size == t:
			max_count += 1
	else:
		stack[0] = i
print(max_size, max_count)


(mx, cnt, st) = (0, 1, [-1])
for (i, w) in enumerate(input().strip()):
	if w == '(':
		st.append(i)
	elif len(st) > 1:
		st.pop()
		_t = i - st[-1]
		if _t > mx:
			(mx, cnt) = (_t, 1)
		elif _t == mx:
			cnt += 1
	else:
		st[0] = i
print(mx, cnt)


from collections import deque
seq = input()
ds = {}
cur = 0
ds[0] = -1
high = 0
count = 0
for (ind, b) in enumerate(seq):
	if b == '(':
		cur += 1
	else:
		del ds[cur]
		cur -= 1
	if cur in ds:
		if ind - ds[cur] > high:
			high = ind - ds[cur]
			count = 1
		elif ind - ds[cur] == high:
			count += 1
	else:
		ds[cur] = ind
if high == 0:
	print(0, 1)
else:
	print(high, count)


bs = input().strip()
n = len(bs)
prevs = [-1] * n
starts = [-1] * n
opens = []
for (i, b) in enumerate(bs):
	if b == '(':
		opens.append(i)
	elif opens:
		j = opens.pop()
		prevs[i] = j
		if starts[j - 1] == -1:
			starts[i] = j
		else:
			starts[i] = starts[j - 1]
best = 0
best_count = 1
for (i, s) in enumerate(starts):
	if s != -1:
		l = i - s + 1
		if l > best:
			best = l
			best_count = 1
		elif l == best:
			best_count += 1
print(best, best_count)


string = input()

def main(string):
	st = []
	answer = [False] * (len(string) + 1)
	for i in range(0, len(string)):
		if string[i] == '(':
			st.append(i)
		else:
			if not st:
				continue
			answer[st.pop()] = True
			answer[i] = True
	res = []
	mx = 0
	for i in range(0, len(answer)):
		if answer[i] == False:
			res.append(mx)
			mx = 0
			continue
		mx += 1
	mx = max(res)
	if mx == 0:
		print(0, 1)
	else:
		print(mx, res.count(mx))
main(string)


import sys
cases = False

def fast_pow(a: int, b: int):
	res = 1
	while b > 0:
		if b & 1:
			res *= a
		a *= a
		b >>= 1
	return res

def c2(n):
	return n * (n - 1) // 2

def get():
	return list(map(int, input().split()))

def bits(n: int):
	return list(bin(n)).count('1')

def main(test_case=False):
	n = int(input()) if test_case else 1
	for _ in range(n):
		test()

def flush():
	sys.stdout.flush()

def parr(arr):
	print(*arr, sep=' ')

def gcd(a, b):
	while b:
		if b % a == 0:
			break
		tmp = a
		a = b % a
		b = tmp
	return a

def ext_gcd(a: int, b: int):
	if b == 0:
		return [a, [1, 0]]
	res = ext_gcd(b, a % b)
	g = res[0]
	x1 = res[1][0]
	y1 = res[1][1]
	x = y1
	y = x1 - y1 * (a // b)
	return [g, [x, y]]
(stack, pair, first) = ([], [], [])

def test():
	global stack, pair, first
	s = list(input())
	n = len(s)
	pair = [-1] * n
	first = [-1] * n
	i = 0
	while i < n:
		if s[i] == '(':
			stack.append(i)
		elif stack:
			d = stack.pop()
			pair[i] = d
			first[i] = d
			if pair[i] > 0 and first[pair[i] - 1] != -1:
				first[i] = first[pair[i] - 1]
		else:
			pair[i] = -1
			first[i] = -1
		i += 1
	i = 0
	mx = 0
	cnt = 1
	while i < n:
		if first[i] == -1:
			i += 1
			continue
		ln = i - first[i] + 1
		if ln > mx:
			mx = ln
			cnt = 1
		elif ln == mx:
			cnt += 1
		i += 1
	print(mx, cnt)
main(cases)


RI = lambda : [int(x) for x in input().split()]
rw = lambda : [input().strip()]
s = list(input().strip())
stack = []
index_stack = -1
stack.append(-1)
index_stack += 1
maxo = 0
c = 0
for i in range(len(s)):
	if s[i] == '(':
		stack.append(i)
		index_stack += 1
	else:
		stack.pop()
		index_stack -= 1
		if len(stack) != 0:
			length_temp = i - stack[index_stack]
			if length_temp > maxo:
				maxo = length_temp
				c = 1
			elif length_temp == maxo:
				c += 1
		else:
			stack.append(i)
			index_stack += 1
if c != 0:
	print(maxo, end=' ')
	print(c)
else:
	print('0 1')


bracket_string = input()
stack = []
max_len = 0
max_len_count = 1
for i in range(len(bracket_string)):
	if bracket_string[i] == ')' and stack and (bracket_string[stack[-1]] == '('):
		stack.pop()
		if stack:
			cur_left_index = stack[-1]
		else:
			cur_left_index = -1
		cur_len = i - cur_left_index
		if cur_len > max_len:
			max_len = cur_len
			max_len_count = 1
		elif cur_len == max_len:
			max_len_count += 1
	else:
		stack.append(i)
print(max_len, max_len_count)


from sys import stdin
(lines, line_index) = (stdin.readlines(), -1)

def get_line():
	global lines, line_index
	line_index += 1
	return lines[line_index]

def main():
	data = get_line().strip()
	max_c = -1
	stack = [-1]
	counter = 0
	for (i, c) in enumerate(data):
		if c == '(':
			stack.append(i)
		else:
			stack.pop()
			if stack:
				temp_max = max(max_c, i - stack[-1])
				if i - stack[-1] == max_c:
					counter += 1
				elif temp_max > max_c:
					counter = 1
					max_c = temp_max
			else:
				stack.append(i)
	if max_c != -1:
		print('%s %s' % (max_c, counter))
	else:
		print('%s %s' % (0, 1))
main()


RI = lambda : [int(x) for x in input().split()]
rw = lambda : [input().strip()]
s = list(input().strip())
dp = [0] * len(s)

def recursor(n):
	if n == 0:
		return 0
	elif n == 1:
		if s[n - 1] == '(':
			return 2
		else:
			return 0
	elif n >= 2:
		if s[n - 1] == '(':
			return dp[n - 2] + 2
		elif n - dp[n - 1] - 1 >= 0 and s[n - dp[n - 1] - 1] == '(':
			if n - dp[n - 1] - 2 >= 0:
				return dp[n - 1] + dp[n - dp[n - 1] - 2] + 2
			else:
				return dp[n - 1] + 2
		else:
			return 0
maxo = 0
c = 0
for i in range(len(s)):
	if s[i] == '(':
		continue
	dp[i] = recursor(i)
	length_temp = dp[i]
	if length_temp > maxo:
		maxo = length_temp
		c = 1
	elif length_temp == maxo and maxo != 0:
		c += 1
if c != 0:
	print(maxo, end=' ')
	print(c)
else:
	print('0 1')


st = [-1]
Max = Count = 0
for (i, c) in enumerate(input()):
	if c == '(':
		st.append(i)
	elif len(st) > 1:
		st.pop()
		temp = i - st[-1]
		if temp > Max:
			Max = temp
			Count = 1
		elif temp == Max:
			Count += 1
	else:
		st[0] = i
if Max:
	print(Max, Count)
else:
	print(0, 1)


a = input()
brakets = []
q = -1
ansmax = 0
quantity = 1
k = 0
for i in range(len(a)):
	if a[i] == '(':
		brakets.append(i)
	elif brakets != []:
		brakets.pop()
		if brakets != []:
			k = i - brakets[-1]
		else:
			k = i - q
		if k > ansmax:
			ansmax = k
			quantity = 1
		elif k == ansmax:
			quantity += 1
	else:
		q = i
print()
print(ansmax, quantity)


def solve(s):
	l = []
	length = ref = 0
	count = 1
	pos = -1
	for i in range(len(s)):
		if s[i] == '(':
			l.append(i)
		elif l:
			l.pop()
			ref = i - l[-1] if l else i - pos
			if ref > length:
				length = ref
				count = 1
			elif ref == length:
				count += 1
		else:
			pos = i
	print(length, count)
s = input()
solve(s)


def main():
	string = input()
	arr = list(string)
	maximum = 0
	freq = 1
	store = []
	for x in range(len(arr)):
		if arr[x] == '(':
			if len(store) == 0:
				store.append(x - 1)
			store.append(x)
		elif len(store) > 0:
			del store[-1]
			if len(store) > 0:
				test = x - store[-1]
				if test > maximum:
					maximum = test
					freq = 1
				elif test == maximum:
					freq += 1
	print(maximum, freq)
main()


s = input()
cnt = ans = 0
n = len(s)
st = [-1]
for i in range(n):
	if s[i] == '(':
		st.append(i)
	elif st[-1] == -1 or s[st[-1]] == ')':
		st.append(i)
	else:
		st.pop()
		if i - st[-1] > ans:
			ans = i - st[-1]
			cnt = 1
		elif i - st[-1] == ans:
			cnt += 1
if ans == 0:
	cnt = 1
print(ans, cnt)


s = input()
d = [-1] * len(s)
e = [-1] * len(s)
stack = []
for (i, c) in enumerate(s):
	if c == '(':
		stack.append(i)
	elif stack:
		f = stack.pop()
		d[i] = f
		e[i] = f
		if e[f - 1] != -1:
			e[i] = e[f - 1]
best = 0
count = 0
for i in range(len(s)):
	if e[i] != -1:
		if best < i - e[i] + 1:
			best = i - e[i] + 1
			count = 0
		if best == i - e[i] + 1:
			count += 1
if best == 0:
	print('0 1')
else:
	print(best, count)


def LongestBracketSequence(s):
	stack = []
	arr = [0] * len(s)
	(max, sum, count) = [0, 0, 0]
	longest_count = 0
	for i in range(len(s)):
		ch = s[i]
		if ch == '(':
			stack.append('(')
		elif ch == ')' and len(stack) != 0:
			top = stack[-1]
			if top == '(':
				stack.pop()
				arr[i] = 2
	for value in reversed(arr):
		if value == 2:
			if count < 0:
				count = 1
				if max < sum:
					max = sum
					longest_count = 1
				elif max == sum:
					longest_count += 1
				sum = 2
			else:
				count += 1
				sum += 2
		else:
			count -= 1
			if count == -1:
				if max < sum:
					max = sum
					longest_count = 1
				elif max == sum:
					longest_count += 1
				sum = 0
	if count == 0 and sum > 0:
		if max < sum:
			max = sum
			longest_count = 1
		elif max == sum:
			longest_count += 1
	if max == 0:
		longest_count = 1
	print(str(max) + ' ' + str(longest_count))
s = input()
LongestBracketSequence(s)


line = input()
res = [0, 1]
Min = [-1 for i in range(len(line) + 1)]
stack = []
for (i, ch) in enumerate(line):
	if ch == '(':
		stack.append(i)
	elif len(stack):
		left = stack.pop()
		right = i
		if Min[left - 1] != -1:
			left = Min[left - 1]
		Min[right] = left
		length = right - left + 1
		if length > res[0]:
			res = [length, 1]
		elif length == res[0]:
			res[1] += 1
print(res[0], res[1])


s = list(input())
stack_o = [-1]
l = 0
m = 0
check = 0
count = 1
for (i, item) in enumerate(s):
	if item == '(':
		stack_o.append(i)
	elif item == ')':
		if len(stack_o) > 1:
			del stack_o[-1]
			l = i - stack_o[-1]
			if l == m:
				count += 1
			elif l > m:
				count = 1
				m = l
		else:
			stack_o[0] = i
print(m, count)


import collections
n = list(input())
stack_b = [0]
stack_pos = [0]
length = 0
lenarray = [0]
counter = 0
for i in range(len(n)):
	if n[i] == '(':
		stack_b.append(i + 1)
		stack_pos.append(i + 1)
	elif len(stack_b) > 1:
		stack_b.pop()
		stack_pos.pop()
		lenarray.append(i + 1 - stack_pos[-1])
	else:
		stack_pos.append(i + 1)
print(max(lenarray), collections.Counter(lenarray)[max(lenarray)])


sequence = [char for char in input().strip()]
stack = []
max_seq = 0
num_max_seq = 1
open_braces_idx = -1
for idx in range(len(sequence)):
	if sequence[idx] == '(':
		stack.append(idx)
	elif stack:
		stack.pop()
		curr_seq = idx - stack[-1] if stack else idx - open_braces_idx
		if curr_seq > max_seq:
			max_seq = curr_seq
			num_max_seq = 1
		elif curr_seq == max_seq:
			num_max_seq += 1
	else:
		open_braces_idx = idx
print(max_seq, num_max_seq)


import os, sys
from io import BytesIO, IOBase

def main():
	s = input().strip()
	st = []
	(maxi, cou) = (0, 1)
	did_it_end = [0] * (len(s) + 1)
	for (ind, i) in enumerate(s):
		if i == '(':
			st.append(ind)
		elif len(st):
			x = st.pop()
			y = ind - x + 1 + did_it_end[x - 1]
			if maxi < y:
				(maxi, cou) = (y, 1)
			elif maxi == y:
				cou += 1
			did_it_end[ind] = y
	print(maxi, cou)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict
s = input()
n = len(s)
dp = [0] * n
st = []
for i in range(n):
	if s[i] == '(':
		st.append(i)
	elif len(st) != 0:
		he = st.pop()
		if he:
			dp[i] = dp[he - 1] + i - he + 1
		else:
			dp[i] = i + 1
ans = 0
cnt = 1
for i in range(n):
	if dp[i] == ans:
		cnt += 1
	elif dp[i] > ans:
		ans = dp[i]
		cnt = 1
if ans == 0:
	cnt = 1
print(ans, cnt)


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
from operator import itemgetter
inp = I()
size = len(inp)
dp = [0] * (size + 1)
que = deque()
for i in range(1, size + 1):
	if inp[i - 1] == '(':
		que.append(i)
	elif que:
		pop = que.pop()
		dp[i] = i - pop + 1 + dp[pop - 1]
mex = max(dp)
cnt = dp.count(mex)
if not mex:
	print(0, 1)
else:
	print(mex, cnt)


class RegularBracket:

	def __init__(self, s):
		self.s = s

	def regular_substring(self):
		st = [-1] * len(self.s)
		cl = [-1] * len(self.s)
		pt = 0
		for i in range(len(self.s)):
			if self.s[i] == '(':
				st[pt] = i
				pt += 1
			elif pt > 0:
				cl[st[pt - 1]] = i + 1
				pt = pt - 1
		pt = 0
		max_len = 0
		segments = []
		while pt < len(self.s):
			if cl[pt] > 0:
				start_pt = pt
				while pt < len(self.s) and cl[pt] > 0:
					pt = cl[pt]
				segments.append((start_pt, pt))
				max_len = max(max_len, pt - start_pt)
			pt += 1
		max_cnt = 0
		for (st, ed) in segments:
			if ed - st == max_len:
				max_cnt += 1
		if max_len == 0:
			print(max_len, 1)
		else:
			print(max_len, max_cnt)
s = input().strip(' ')
rg = RegularBracket(s)
rg.regular_substring()


from collections import defaultdict
s = input()
stack = []
dct = defaultdict(int)
n = len(s)
d = [-1 for i in range(n)]
c = [-1 for i in range(n)]
i = 0
while i < n:
	if s[i] == '(':
		stack.append(i)
	elif stack == []:
		None
	else:
		d[i] = stack.pop()
		if c[d[i] - 1] != -1:
			c[i] = c[d[i] - 1]
		else:
			c[i] = d[i]
	i += 1
_max = 0
count = 1
for i in range(n):
	if c[i] != -1:
		temp = i - c[i] + 1
		if temp > _max:
			_max = temp
			count = 1
		elif temp == _max:
			count += 1
print(_max, count)


__author__ = 'Darren'

def solve():
	sequence = input().strip()
	n = len(sequence)
	(longest, count, start) = (0, 1, 0)
	stack = []
	for i in range(n):
		if sequence[i] == '(':
			stack.append(i)
		else:
			if len(stack) == 0:
				start = i + 1
				continue
			stack.pop()
			if len(stack) == 0:
				current_length = i - start + 1
				if current_length > longest:
					longest = current_length
					count = 1
				elif current_length == longest:
					count += 1
				else:
					pass
			else:
				current_length = i - stack[-1]
				if current_length > longest:
					longest = current_length
					count = 1
				elif current_length == longest:
					count += 1
				else:
					pass
	print('%d %d' % (longest, count))
solve()


s = input()
(dp, m, c, mx) = ([0], {0: -1}, 0, 0)
for i in range(len(s)):
	if s[i] == '(':
		dp.append(0)
		c += 1
	else:
		c -= 1
		j = m.get(c, -2)
		if j == -2:
			dp.append(0)
		else:
			dp.append(dp[j + 1] + i - j)
		mx = max(mx, dp[-1])
	m[c] = i
print(*([mx, dp.count(mx)] if mx else '01'))


inp = input()
(maxlen, occur, stack) = (0, 1, [-1])
for (i, val) in enumerate(inp):
	if val == '(':
		stack.append(i)
	elif len(stack) > 1:
		stack.pop()
		consq = i - stack[-1]
		if maxlen < consq:
			(maxlen, occur) = (consq, 1)
		elif maxlen == consq:
			occur += 1
	else:
		stack[0] = i
print(maxlen, occur)


from sys import stdin, stdout
s = stdin.readline().rstrip('\n')
n = len(s)
l1 = [-1] * n
l2 = [-1] * n
l3 = [0] * (n + 1)
l = []
for i in range(n):
	if s[i] == '(':
		l.append(i)
	elif len(l):
		a = l[-1]
		l.pop()
		l1[i] = i
		if a != 0:
			if l2[a - 1] != -1:
				l2[i] = l2[a - 1]
			else:
				l2[i] = a
		else:
			l2[i] = 0
		l3[l1[i] - l2[i] + 1] += 1
(ans1, ans2) = (0, 1)
for i in range(n, -1, -1):
	if l3[i] != 0:
		ans1 = i
		ans2 = l3[i]
		break
print(ans1, ans2)


(a, b) = ([], [])
for (i, x) in enumerate(input()):
	if x == '(':
		b.append(i)
	elif b:
		j = b.pop()
		while a and a[-1][0] > j:
			a.pop()
		if a and a[-1][1] == j - 1:
			a.append((a.pop()[0], i))
		else:
			a.append((j, i))
(m, n) = (0, 1)
for x in a:
	l = x[1] - x[0] + 1
	if l > m:
		(m, n) = (l, 1)
	elif l == m:
		n += 1
print(m, n)


def main():
	m = cnt = 1
	stack = [1]
	for c in input():
		if c == '(':
			stack.append(1)
		elif len(stack) < 2:
			stack[0] = 1
		else:
			x = stack.pop() + stack.pop() + 1
			if m < x:
				(m, cnt) = (x, 1)
			elif m == x:
				cnt += 1
			stack.append(x)
	print(m - 1, cnt)
main()


from collections import deque, defaultdict
s = input()
mp = defaultdict(int)
stack = deque([-1])
_max = 0
for (i, c) in enumerate(s):
	if c == '(':
		stack.append(i)
	else:
		last = stack.pop()
		if len(stack) == 0:
			stack.append(i)
		else:
			curr = i - stack[-1]
			if curr > _max:
				_max = curr
			mp[curr] += 1
if _max == 0:
	print(0, 1)
else:
	print(_max, mp[_max])


import sys
from collections import defaultdict
from time import time
from typing import Tuple
(OPEN, CLOSE) = ('(', ')')

def magic(data: Tuple):
	(open_index, open_num, step) = (0, 0, 0)
	chars_count = len(data) - 1
	open_indexes = []
	x = []
	while step <= chars_count:
		char = data[step]
		if char == OPEN:
			open_indexes.append(step)
			open_num += 1
		elif char == CLOSE and open_num > 0:
			open_num -= 1
			open_index = open_indexes.pop()
			yield open_index
			yield step
		step += 1
	return data

def solve(string):
	(group, prev) = (0, 0)
	(maxgroup, maxgroupcount) = (0, 0)
	for index in sorted(magic(tuple(string.strip()))):
		sub = index - prev
		if sub == 1 or sub == index:
			group += 1
		elif group > 0:
			if maxgroup == group:
				maxgroupcount += 1
			if maxgroup < group:
				maxgroup = group
				maxgroupcount = 1
			group = 1
		prev = index
	if maxgroup < group:
		maxgroup = group
		maxgroupcount = 1
	elif maxgroup == group:
		maxgroupcount += 1
	return '%s %s' % (maxgroup, maxgroupcount)
print(solve(sys.stdin.readline()))


import os
import sys
from io import BytesIO, IOBase

def main():
	arr = input()
	stack = []
	n = len(arr)
	idx = [-1] * (n + 1)
	extension = [-1] * (n + 1)
	mx = 0
	ans = 1
	for (i, item) in enumerate(arr):
		if item == '(':
			stack.append(i)
		elif stack:
			z = stack.pop()
			idx[i] = z
			if z and idx[z - 1] != -1:
				extension[i] = extension[z - 1]
			else:
				extension[i] = z
			zz = i - extension[i] + 1
			if mx < zz:
				mx = zz
				ans = 1
			elif mx == zz:
				ans += 1
		else:
			idx[i] = -1
	print(mx, ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


string = input()
stack = []
arr = []
for i in range(len(string)):
	f = True
	if stack:
		if string[stack[-1]] == '(' and string[i] == ')':
			stack.pop()
			f = False
	if f:
		stack += (i,)
stack = [-1] + stack + [len(string)]
for i in range(0, len(stack) - 1):
	if stack[i + 1] - stack[i] - 1 > 0:
		arr += (stack[i + 1] - stack[i] - 1,)
if len(arr) == 0:
	print(0, 1)
else:
	print(max(arr), arr.count(max(arr)))


from collections import deque
s = input()
stack = deque()
ls = [0] * 1000000
ans = -1
for i in range(len(s)):
	if s[i] == ')':
		if stack:
			r = stack.pop()
			ls[i] = ls[r - 1] + (i - r + 1)
	else:
		stack.append(i)
f_ans = max(ls)
count = ls.count(f_ans)
if f_ans <= 0:
	print(0, 1)
else:
	print(f_ans, count)


s = input()
n = len(s)
stack = []
early = [-1] * n
corrs = [-1] * n
for i in range(n):
	if s[i] == '(':
		stack.append(i)
	elif stack:
		corrs[i] = early[i] = stack.pop()
		if early[i] and s[early[i] - 1] == ')' and (early[early[i] - 1] != -1):
			early[i] = early[early[i] - 1]
	else:
		early[i] = corrs[i] = -1
record = 0
count = 0
for i in range(n):
	if early[i] == -1:
		continue
	length = i - early[i] + 1
	if length > record:
		record = length
		count = 1
	elif length == record:
		count += 1
if record == 0:
	print(0, 1)
else:
	print(record, count)


import sys
s = sys.stdin.readline().rstrip()
balance = 0
balanceRecord = {0: -1}
minBalance = 0
maxLen = 0
maxCount = 1
for i in range(len(s)):
	if s[i] == '(':
		balance += 1
	else:
		balance -= 1
	if balance < minBalance:
		minBalance = balance
		balanceRecord = {}
	if balance in balanceRecord:
		balanceRecord.pop(balance + 1)
		newLen = i - balanceRecord[balance]
		if newLen > maxLen:
			maxLen = newLen
			maxCount = 1
		elif newLen == maxLen:
			maxCount += 1
	else:
		balanceRecord[balance] = i
print(str(maxLen) + ' ' + str(maxCount))


l = input()
m = len(l)
max_d = 0
d = [-1] * m
c = [-1] * m
dis = [-1] * m
times = 1
stack = []
for i in range(m):
	if l[i] is '(':
		stack.append(i)
	elif stack:
		d[i] = stack.pop()
		c[i] = d[i]
		dis[i] = i - c[i] + 1
		if d[d[i] - 1] != -1:
			c[i] = c[d[i] - 1]
			dis[i] = i - c[i] + 1
		if dis[i] > max_d:
			max_d = dis[i]
			times = 1
		elif dis[i] == max_d:
			times += 1
print(max_d, times)


s = input()
n = len(s)
dem1_max = 0
dem2_max = 1
A = [-1]
for i in range(n):
	if s[i] == '(':
		A.append(i)
	elif len(A) > 1:
		x = A.pop()
		u = i - A[-1]
		if u == dem1_max:
			dem2_max += 1
		elif u >= dem1_max:
			dem1_max = u
			dem2_max = 1
	else:
		A[0] = i
print('{} {}'.format(dem1_max, dem2_max))