This is a harder version of the problem. In this version, n ≤ 300 000.

Vasya is an experienced developer of programming competitions' problems. As all great minds at some time, Vasya faced a creative crisis. To improve the situation, Petya gifted him a string consisting of opening and closing brackets only. Petya believes, that the beauty of the bracket string is a number of its cyclical shifts, which form a correct bracket sequence.

To digress from his problems, Vasya decided to select two positions of the string (not necessarily distinct) and swap characters located at this positions with each other. Vasya will apply this operation exactly once. He is curious what is the maximum possible beauty he can achieve this way. Please help him.

We remind that bracket sequence s is called correct if: 

  * s is empty; 
  * s is equal to "(t)", where t is correct bracket sequence; 
  * s is equal to t_1 t_2, i.e. concatenation of t_1 and t_2, where t_1 and t_2 are correct bracket sequences. 



For example, "(()())", "()" are correct, while ")(" and "())" are not.

The cyclical shift of the string s of length n by k (0 ≤ k < n) is a string formed by a concatenation of the last k symbols of the string s with the first n - k symbols of string s. For example, the cyclical shift of string "(())()" by 2 equals "()(())".

Cyclical shifts i and j are considered different, if i ≠ j.

Input

The first line contains an integer n (1 ≤ n ≤ 300 000), the length of the string.

The second line contains a string, consisting of exactly n characters, where each of the characters is either "(" or ")".

Output

The first line should contain a single integer — the largest beauty of the string, which can be achieved by swapping some two characters.

The second line should contain integers l and r (1 ≤ l, r ≤ n) — the indices of two characters, which should be swapped in order to maximize the string's beauty.

In case there are several possible swaps, print any of them.

Examples

Input


10
()()())(()


Output


5
8 7


Input


12
)(()(()())()


Output


4
5 10


Input


6
)))(()


Output


0
1 1

Note

In the first example, we can swap 7-th and 8-th character, obtaining a string "()()()()()". The cyclical shifts by 0, 2, 4, 6, 8 of this string form a correct bracket sequence.

In the second example, after swapping 5-th and 10-th character, we obtain a string ")(())()()(()". The cyclical shifts by 11, 7, 5, 3 of this string form a correct bracket sequence.

In the third example, swap of any two brackets results in 0 cyclical shifts being correct bracket sequences.

Difficulty: VERY_HARD
Tags: Implementation

Starter code:

Solutions:
def get_bal():
	bal = [0] * n
	bal[0] = u[0]
	for i in range(1, n):
		bal[i] = bal[i - 1] + u[i]
	min_b = min(bal)
	ans = 0
	for i in range(n):
		if bal[i] == min_b:
			ans += 1
	return ans
n = int(input())
u = list(input())
for i in range(n):
	if u[i] == '(':
		u[i] = 1
	else:
		u[i] = -1
if sum(u) != 0:
	print(0)
	print(1, 1)
	exit()
ind = (-1, -1)
ans = -1
for i in range(n):
	for j in range(i, n):
		(u[i], u[j]) = (u[j], u[i])
		ans_i = get_bal()
		(u[i], u[j]) = (u[j], u[i])
		if ans_i > ans:
			ans = ans_i
			ind = (i + 1, j + 1)
print(ans)
print(ind[0], ind[1])


n = int(input())
S = list(input())

def count_all(s):
	cnt = 0
	l_cnt = 1
	for c in s[1:]:
		if c == ')':
			l_cnt -= 1
		else:
			l_cnt += 1
		if l_cnt == 0:
			cnt += 1
	return cnt
if S == list('()' * (n // 2)) or S == list(')' + '()' * (n // 2 - 1) + '('):
	print(n // 2)
	print(1, 1)
else:
	res = 0
	(l, r) = (1, 1)
	lc = rc = 0
	for c in S:
		if c == '(':
			lc += 1
		else:
			rc += 1
	if lc == rc:
		for i in range(n):
			for j in range(i, n):
				ss = S[:]
				if ss[i] == ss[j]:
					continue
				(ss[i], ss[j]) = (ss[j], ss[i])
				t = 0
				t_min = n
				m = 0
				for k in range(n):
					if ss[k] == ')':
						t -= 1
					else:
						t += 1
					if t < t_min:
						(t_min, m) = (t, k)
				sss = ss[m + 1:] + ss[:m + 1]
				temp = count_all(sss)
				if temp >= res:
					res = temp
					(l, r) = (i + 1, j + 1)
	print(res)
	print(l, r)


import sys
input = sys.stdin.readline

def matcher(correcti):
	open_ = 0
	close_ = 0
	count = 0
	excess = 0
	for i in range(len(correcti)):
		if correcti[i] == '(':
			open_ += 1
		if correcti[i] == ')':
			close_ += 1
		if close_ > open_ and open_ == 0:
			excess += 1
			close_ -= 1
			count = 0
			continue
		if open_ == close_:
			count += 1
			open_ = 0
			close_ = 0
	if open_ - close_ == excess:
		if excess > 0:
			return count + 1
		else:
			return count
	else:
		return 0
n = int(input())
l = [i for i in input() if i != '\n']
st = ''.join(l).rstrip(')').rstrip('(')
swap = matcher(l[len(st):] + l[:len(st)])
shifts = [[1, 1]]
for i in range(n):
	for j in range(i, n):
		if l[i] != l[j]:
			(l[i], l[j]) = (l[j], l[i])
			output = matcher(l)
			if output > swap:
				swap = output
				shifts[0] = [i + 1, j + 1]
			(l[i], l[j]) = (l[j], l[i])
print(swap)
print(*shifts[0])


n = int(input())
s = [1 if c == '(' else -1 for c in input()]
if s.count(1) != s.count(-1):
	print(0)
	print(1, 1)
	exit()
ans = 0
pair = (1, 1)
for i in range(n - 1):
	for j in range(i, n):
		(s[i], s[j]) = (s[j], s[i])
		(min_p, cnt) = (10 ** 9, 0)
		nest = 0
		for k in range(n):
			nest += s[k]
			if min_p > nest:
				min_p = nest
				cnt = 1
			elif min_p == nest:
				cnt += 1
		if ans < cnt:
			ans = cnt
			pair = (i + 1, j + 1)
		(s[i], s[j]) = (s[j], s[i])
print(ans)
print(*pair)


import os, sys
from io import BytesIO, IOBase

def calc(s):
	pref = [0]
	pref_min = [pref[0]]
	for i in s:
		pref.append(pref[-1] + i)
		pref_min.append(min(pref_min[-1], pref[-1]))
	return (pref_min, pref)

def main():
	n = int(input())
	s = list(input().strip())
	for i in range(n):
		if s[i] == '(':
			s[i] = 1
		else:
			s[i] = -1
	if 2 * s.count(1) != n:
		print(0)
		print(1, 1)
		exit()
	(pref, pr) = calc(s)
	(val, ans, ind, suff) = (0, 0, [1, 1], pr[n])
	for i in range(n):
		if val + pref[n - i] >= 0 and suff == pr[n - i]:
			ans += 1
		val += s[n - 1 - i]
		suff = min(suff, pr[n - 1 - i])
	for i in range(n):
		for j in range(i + 1, n):
			if s[i] == s[j]:
				continue
			(s[i], s[j]) = (s[j], s[i])
			(pref, pr) = calc(s)
			(ans1, val, suff) = (0, 0, pr[n])
			for ii in range(n):
				if suff == pr[n - ii] and val + pref[n - ii] >= 0:
					ans1 += 1
				val += s[n - 1 - ii]
				suff = min(suff, pr[n - 1 - ii])
			if ans1 > ans:
				(ind, ans) = ([i + 1, j + 1], ans1)
			(s[i], s[j]) = (s[j], s[i])
	print(ans)
	print(*ind)
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 deque

def getAnsRight(a):
	stack = deque()
	ans = 0
	for i in range(len(a)):
		if a[i] == '(':
			stack.append(a[i])
		else:
			stack.pop()
		if not len(stack):
			ans += 1
	return ans

def getAnsRighnt(a):
	stack = deque()
	indClose = -1
	indOpen = -1
	for i in range(len(a)):
		if a[i] == '(':
			stack.append((a[i], i))
		if a[i] == ')':
			if len(stack) == 0:
				indClose = i
			else:
				stack.pop()
	if len(stack):
		indOpen = stack.popleft()[1]
	if indOpen == -1 and indClose == -1:
		return getAnsRight(a)
	return 1 + getAnsRight(a[indClose + 1:indOpen])

def getPer(a, i, j):
	l = a[i]
	a[i] = a[j]
	a[j] = l
	sOpen = 0
	sClose = 0
	for i in range(len(a)):
		if a[i] == '(':
			sOpen += 1
		else:
			sClose += 1
	if sOpen != sClose:
		return 0
	return getAnsRighnt(a)

def kek():
	n = int(input())
	a = list(input())
	answr = getPer(a, 0, 0)
	indL = 0
	indR = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if a[i] == a[j]:
				continue
			lastAnswer = answr
			answr = max(getPer(a.copy(), i, j), answr)
			if lastAnswer < answr:
				indL = i
				indR = j
	print(answr)
	print(indL + 1, indR + 1)
kek()


import sys

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

def input():
	return sys.stdin.readline().rstrip('\n')

def oint():
	return int(input())
n = oint()
stemp = input()
s = []
for i in range(n):
	if stemp[i] == '(':
		s.append(1)
	else:
		s.append(-1)
maxcnt = 0
candi = [0, 0]
for l in range(n):
	for r in range(l, n):
		cnt = 0
		(s[l], s[r]) = (s[r], s[l])
		ssum = [0] * n
		ssum[0] = s[0]
		for i in range(1, n):
			ssum[i] = ssum[i - 1] + s[i]
		minssum = min(ssum)
		if ssum[n - 1] != 0:
			continue
		for i in range(0, n):
			if ssum[i] == minssum:
				cnt += 1
		if maxcnt < cnt:
			candi = [r, l]
			maxcnt = cnt
		(s[l], s[r]) = (s[r], s[l])
print(maxcnt)
print(candi[0] + 1, candi[1] + 1)


n = int(input())
seq = list(input())

def get_comps(seq):
	depth = 0
	components = 0
	lookingfor = 0
	for i in range(n):
		if seq[i] == '(':
			depth += 1
		else:
			depth -= 1
			if depth < lookingfor:
				lookingfor = depth
				components = 1
			elif depth == lookingfor:
				components += 1
	return components

def other(x):
	if x == '(':
		return ')'
	return '('
if n % 2 == 1 or seq.count('(') != seq.count(')'):
	print(0)
	print(1, 1)
else:
	best1 = 1
	best2 = 1
	bestVal = get_comps(seq)
	for i in range(n):
		for j in range(i + 1, n):
			if seq[i] != seq[j]:
				seq[i] = other(seq[i])
				seq[j] = other(seq[j])
				val = get_comps(seq)
				if val > bestVal:
					best1 = i
					best2 = j
					bestVal = val
				seq[i] = other(seq[i])
				seq[j] = other(seq[j])
	print(bestVal)
	print(best1 + 1, best2 + 1)


import sys
from collections import Counter

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
N = INT()
S = list(input())
C = Counter(S)
if C['('] != C[')']:
	print(0)
	print(1, 1)
	exit()

def check(S):
	cur = cnt = mn = 0
	for s in S:
		if s == '(':
			cur += 1
		else:
			cur -= 1
		if cur < mn:
			mn = cur
			cnt = 1
		elif cur == mn:
			cnt += 1
	return cnt
mx = 0
ans = (1, 1)
for i in range(N):
	for j in range(i + 1, N):
		(S[i], S[j]) = (S[j], S[i])
		cnt = check(S)
		if cnt > mx:
			mx = cnt
			ans = (i + 1, j + 1)
		(S[i], S[j]) = (S[j], S[i])
print(mx)
print(*ans)


n = int(input())
s = input()
maxn = -1
if n == 1:
	print(0)
	print(1, 1)
	exit(0)
for i in range(n):
	for j in range(i + 1, n):
		s1 = s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
		num = 0
		temp = 0
		min = 501
		for k in range(n):
			if s1[k] == '(':
				temp += 1
			else:
				temp -= 1
			if temp < min:
				min = temp
				num = 1
			elif temp == min:
				num += 1
		if temp != 0:
			print(0)
			print(1, 1)
			exit(0)
		if num > maxn:
			maxn = num
			ansi = i + 1
			ansj = j + 1
print(maxn)
print(ansi, ansj)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
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')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

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

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = 0
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][0] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
n = int(input())
s = list(input())
L = 1
R = 1

def check():
	calc = 0
	min = 0
	cntmin = 0
	for ch in s:
		if ch == '(':
			calc += 1
		else:
			calc -= 1
		if min > calc:
			min = calc
			cntmin = 1
		elif min == calc:
			cntmin += 1
	return cntmin if calc == 0 else 0
best = check()
for i in range(n):
	for j in range(i + 1, n, 1):
		(s[i], s[j]) = (s[j], s[i])
		new = check()
		(s[j], s[i]) = (s[i], s[j])
		if new > best:
			best = new
			L = 1 + i
			R = 1 + j
print(best)
print(L, R)


n = int(input())
st = input()
s = [0 if c == '(' else 1 for c in st]
if n % 2 != 0 or sum(s) != n // 2:
	print(0)
	print(1, 1)
	exit(0)
maxx = 0
ind = (0, 0)
maxshift = 0
for shift in range(n):
	stack = 0
	x1 = -1
	x2 = -1
	sumzero = 0
	for (i, c) in enumerate(s):
		if s[(i + shift) % n] == 0:
			stack += 1
		else:
			stack -= 1
		if stack == 0:
			sumzero += 1
		if stack < 0:
			x1 = i
			break
	stack = 0
	for i in range(n - 1, -1, -1):
		if s[(i + shift) % n] == 1:
			stack += 1
		else:
			stack -= 1
		if stack < 0:
			x2 = i
			break
	if x1 == -1 and x2 == -1 and (stack == 0):
		if sumzero > maxx:
			maxx = sumzero
			ind = (0, 0)
	if x1 == -1 or x2 == -1 or x1 == x2:
		continue
	stack = 0
	corr = True
	ans = 0
	for i in range(n):
		c = s[(i + shift) % n]
		if i == x1 or i == x2:
			c = 1 - c
		if c == 0:
			stack += 1
		else:
			stack -= 1
		if stack == 0:
			ans += 1
		if stack == -1:
			corr = False
			break
	if not corr or stack > 0:
		continue
	if ans > maxx:
		maxshift = shift
		maxx = ans
		ind = ((x1 + shift) % n, (x2 + shift) % n)
print(maxx)
print(ind[0] + 1, ind[1] + 1)


n = int(input().strip())
s = input().strip()
ss = 0
mina = 0
ti = 0
for k in range(len(s)):
	if s[k] == '(':
		ss += 1
	else:
		ss -= 1
	if ss < 0:
		ti = k + 1
		ss = 0
s = s[ti:] + s[:ti]
ss = 0
for k in range(len(s)):
	if s[k] == '(':
		ss += 1
	else:
		ss -= 1
	if ss < 0:
		print(0)
		print(1, 1)
		break
else:
	if ss == 0:
		pre = [0 for k in range(len(s))]
		ss = 0
		for k in range(len(s)):
			if s[k] == '(':
				ss += 1
			else:
				ss -= 1
			pre[k] = ss
		tt = 0
		a = (1, 1)
		for k in range(0, len(s)):
			if pre[k] == 0:
				tt += 1
		maxi = tt
		g = 0
		gg = 0
		while gg < len(s):
			if pre[gg] == 0:
				if gg != g + 1:
					yy = g + 1
					y = g + 1
					q = 0
					while yy < gg:
						if pre[yy] == 1:
							if yy != y + 1:
								rr = y + 1
								r = y + 1
								h = 0
								while rr < yy:
									if pre[rr] == 2:
										h += 1
									rr += 1
								if tt + h + 1 > maxi:
									maxi = tt + h + 1
									a = (y, yy)
							elif tt + 1 > maxi:
								maxi = tt + 1
								a = (y, yy)
							q += 1
							y = yy + 1
							yy = y
						else:
							yy += 1
					if q + 1 > maxi:
						maxi = q + 1
						a = (g, gg)
				g = gg + 1
				gg = g
			else:
				gg += 1
		print(maxi)
		print((a[0] + ti) % len(s) + 1, (a[1] + ti) % len(s) + 1)
	else:
		print(0)
		print(1, 1)


n = int(input())
s = list(input())
best = 0
L = 1
R = 1
if n % 2:
	print(best)
	print(L, R)
	quit()

def check():
	calc = 0
	min = 0
	cntmin = 0
	for ch in s:
		if ch == '(':
			calc += 1
		else:
			calc -= 1
		if min > calc:
			min = calc
			cntmin = 1
		elif min == calc:
			cntmin += 1
	return cntmin if calc == 0 else 0
best = check()
for (i, ch) in enumerate(s, 0):
	for j in range(i + 1, n, 1):
		(s[i], s[j]) = (s[j], s[i])
		new = check()
		(s[j], s[i]) = (s[i], s[j])
		if new > best:
			best = new
			L = 1 + i
			R = 1 + j
print(best)
print(L, R)


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

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

def bcheck(a, l, r):
	a1 = a[:]
	(a1[l], a1[r]) = (a1[r], a1[l])
	N = len(a)
	(p, n) = ([], [])
	for i in range(N):
		if a1[i] == ')':
			if p:
				p.pop()
			else:
				n.append(i)
		else:
			p.append(i)
	l = len(p)
	rt = 0
	if l > 0:
		rt = n[-1] + 1
	if rt:
		a1 = a1[rt:] + a1[:rt]
	(ch, pt) = (0, 0)
	for i in a1:
		if i == '(':
			pt += 1
		else:
			pt -= 1
		if pt == 0:
			ch += 1
	return ch

def main():
	N = iin()
	a = list(input())
	(c1, c2) = (a.count(')'), a.count('('))
	if c1 != c2 or N % 2:
		print(0)
		print(1, 1)
	else:
		mx = [-1, 0, 0]
		for i in range(N):
			for j in range(i + 1, N):
				if a[i] != a[j]:
					val = bcheck(a, i, j)
					if mx[0] < val:
						mx = [val, i, j]
		a1 = a[:]
		N = len(a)
		(p, n) = ([], [])
		for i in range(N):
			if a1[i] == ')':
				if p:
					p.pop()
				else:
					n.append(i)
			else:
				p.append(i)
		l = len(p)
		rt = 0
		if l > 0:
			rt = n[-1] + 1
		if rt:
			a1 = a1[rt:] + a1[:rt]
		(ch, pt) = (0, 0)
		for i in a1:
			if i == '(':
				pt += 1
			else:
				pt -= 1
			if pt == 0:
				ch += 1
		if ch > mx[0]:
			print(ch)
			print(1, 1)
		else:
			print(mx[0])
			print(mx[1] + 1, mx[2] + 1)
main()


n = int(input())
s = input()
sl = list(s)
ans = 0
ai = [1, 1]
if sl.count('(') == sl.count(')'):
	for i in range(n):
		for j in range(i + 1, n):
			(sl[i], sl[j]) = (sl[j], sl[i])
			b = 0
			p = 0
			minp = 0
			k = 0
			for kk in range(n):
				if sl[k] == '(':
					p += 1
				else:
					p -= 1
					if p == minp:
						b += 1
					elif p < minp:
						minp = p
						b = 1
				k = (k + 1) % n
			if b > ans:
				ans = b
				ai = [i + 1, j + 1]
			(sl[i], sl[j]) = (sl[j], sl[i])
print(ans)
print(ai[0], ai[1])


n = int(input())
s = input()
r = 0
l = n - 1
root = []
buf = []
to_the_right = True
for count in range(n):
	if to_the_right:
		i = r
		r += 1
	else:
		i = l
		l -= 1
	b = s[i]
	if b == '(':
		if len(buf) == 0 or buf[-1][0] != -1:
			buf.append([-1, -1, []])
		buf[-1][0] = i
	else:
		if len(buf) == 0 or buf[-1][1] != -1:
			buf.append([-1, -1, root])
			root = []
			to_the_right = False
		buf[-1][1] = i
	if buf[-1][0] != -1 and buf[-1][1] != -1:
		tmp = buf.pop()
		if len(buf):
			buf[-1][2].append(tmp)
		else:
			root.append(tmp)
			to_the_right = True
sol = [[0, 1, 1]]
if len(buf) == 0:
	sol.append([len(root), 1, 1])
	for child in root:
		sol.append([len(child[2]) + 1, child[0] + 1, child[1] + 1])
		for gr_child in child[2]:
			sol.append([len(root) + len(gr_child[2]) + 1, gr_child[0] + 1, gr_child[1] + 1])
print('%d\n%d %d' % tuple(max(sol)))


n = int(input())
s = list(input())
if n % 2 == 1 or s.count('(') != s.count(')'):
	print('0\n1 1')
	exit()

def solve():
	(cnt_open, res, need) = (0, 0, 0)
	for i in s:
		if i == '(':
			cnt_open += 1
		else:
			cnt_open -= 1
			if cnt_open < need:
				need = cnt_open
				res = 1
			elif cnt_open == need:
				res += 1
	return res
(res, res_i, res_j) = (solve(), 0, 0)
for i in range(n):
	for j in range(i + 1, n):
		if s[i] != s[j]:
			(s[i], s[j]) = (s[j], s[i])
			curr = solve()
			(s[i], s[j]) = (s[j], s[i])
			if curr > res:
				res = curr
				res_i = i
				res_j = j
print(res)
print(res_i + 1, res_j + 1)


n = int(input())
ddd = input()
d = [0]
for dd in ddd:
	if dd == '(':
		d.append(d[-1] + 1)
	else:
		d.append(d[-1] - 1)
if d[-1] != 0:
	print('0\n1 1')
	exit(0)
d.pop()
mn = min(d)
ind = d.index(mn)
d = d[ind:] + d[:ind]
d = [i - mn for i in d]
fi = -1
crfi = -1
li = -1
mx = 0
cr = 0
cnt0 = 0
for i in range(n):
	dd = d[i]
	if dd == 0:
		cnt0 += 1
	if dd == 2:
		if cr == 0:
			crfi = i
		cr += 1
		if cr > mx:
			fi = crfi
			li = i
			mx = cr
	elif dd < 2:
		cr = 0
if fi == -1:
	ans1 = [cnt0, 0, 0]
else:
	ans1 = [cnt0 + mx, fi - 1, li]
fi = -1
crfi = -1
li = -1
mx = 0
cr = 0
for i in range(n):
	dd = d[i]
	if dd == 1:
		if cr == 0:
			crfi = i
		cr += 1
		if cr > mx:
			fi = crfi
			li = i
			mx = cr
	elif dd < 1:
		cr = 0
ans2 = [mx, fi - 1, li]
if ans1[0] > ans2[0]:
	print(ans1[0])
	print((ans1[1] + ind) % n + 1, (ans1[2] + ind) % n + 1)
else:
	print(ans2[0])
	print((ans2[1] + ind) % n + 1, (ans2[2] + ind) % n + 1)


def prefix(s):
	count = 0
	cur = 0
	m = 0
	for c in s:
		if c == '(':
			cur += 1
		else:
			cur -= 1
		if cur < m:
			m = cur
			count = 0
		if cur == m:
			count += 1
	return count
from collections import Counter
n = int(input())
s = list(input())
C = Counter(s)
if C['('] == C[')']:
	(a, b, c) = (-1, -1, -1)
	for l in range(n):
		for r in range(l, n):
			(s[l], s[r]) = (s[r], s[l])
			abc = prefix(s)
			if abc > a:
				a = abc
				b = l
				c = r
			(s[l], s[r]) = (s[r], s[l])
	print(a)
	print(b + 1, c + 1)
else:
	print(0)
	print(1, 1)


N = int(input())
string = list(input())

def even(string):
	a = 0
	b = 0
	for c in string:
		if c == ')':
			a += 1
		if c == '(':
			b += 1
	return a == b

def swap(arr, i, j):
	(arr[i], arr[j]) = (arr[j], arr[i])

def calc(string):
	N = len(string)
	l = 0
	s = 0
	for char in string:
		if char == '(':
			s += 1
		else:
			s -= 1
		l = min(l, s)
	if s != 0:
		return 0
	t = 0
	for i in range(N):
		c = string[i]
		if c == '(':
			s += 1
			if s - l <= 1:
				t += 1
		else:
			s -= 1
	return t
if even(string):
	highest = calc(string)
	a = b = 0
	for i in range(N):
		for j in range(i + 1, N):
			if string[i] == string[j]:
				continue
			swap(string, i, j)
			total = calc(string)
			if total > highest:
				highest = total
				(a, b) = (i, j)
			swap(string, i, j)
	print(highest)
	print(a + 1, b + 1)
else:
	print(0)
	print(1, 1)


n = int(input())
s = list(input())

def call(x):
	if x == '(':
		return 1
	else:
		return -1
s = list(map(call, s))
if sum(s) != 0:
	print(0)
	print(1, 1)
else:
	ans = 0
	pr = (1, 1)
	for i in range(n - 1):
		for j in range(i, n):
			lm = 10 ** 9
			sm = 0
			ct = 0
			(s[i], s[j]) = (s[j], s[i])
			for k in range(n):
				sm += s[k]
				if sm < lm:
					lm = sm
					ct = 1
				elif sm == lm:
					ct += 1
			if ct > ans:
				ans = ct
				pr = (i + 1, j + 1)
			(s[i], s[j]) = (s[j], s[i])
	print(ans)
	print(*pr)


n = int(input())
s = input()
res = 0
(ri, rj) = (0, 0)
for i in range(n):
	for j in range(i + 1, n):
		ss = s[:i] + s[j] + s[i + 1:j] + s[i] + s[j + 1:]
		(k_mn, mn) = (0, 0)
		teck = 0
		for g in range(n):
			if ss[g] == '(':
				teck += 1
			else:
				teck -= 1
			if k_mn == 0 or teck < mn:
				(mn, k_mn) = (teck, 1)
			elif teck == mn:
				k_mn += 1
		if teck == 0:
			if k_mn > res:
				res = max(res, k_mn)
				ri = i
				rj = j
print(res)
print(ri + 1, rj + 1)


import math as mt
import collections as cc
import sys
I = lambda : set(map(int, input().split()))
(n,) = I()
s = list(input())
tf = 0
l = 1
r = 1
for i in range(n):
	for j in range(i + 1, n):
		ans = 0
		(s[i], s[j]) = (s[j], s[i])
		ch = 0
		cnt = 0
		cm = 0
		for k in s:
			if k == '(':
				ch += 1
			else:
				ch -= 1
			if ch < cm:
				cm = ch
				cnt = 1
			elif ch == cm:
				cnt += 1
		if ch == 0 and cnt > tf:
			tf = cnt
			l = i + 1
			r = j + 1
		(s[i], s[j]) = (s[j], s[i])
print(tf)
print(l, r)


def beauty(tt):
	depth = 0
	min_depth = 0
	dd = []
	for (i, t) in enumerate(tt):
		if t == '(':
			depth += 1
		else:
			depth -= 1
		dd.append(depth)
		if depth < min_depth:
			min_depth = depth
	if depth != 0:
		return 0
	result = 0
	for d in dd:
		if d == min_depth:
			result += 1
	return result

def main():
	n = int(input())
	if n % 2 == 1:
		print(0)
		print(1, 1)
		return
	tt = input()
	best = beauty(tt)
	l = 1
	r = 1
	for i in range(n - 1):
		for j in range(i + 1, n):
			if tt[i] != tt[j]:
				ttt = list(tt)
				ttt[i] = tt[j]
				ttt[j] = tt[i]
				b = beauty(ttt)
				if b > best:
					best = b
					l = i + 1
					r = j + 1
	print(best)
	print(l, r)
main()


n = int(input())
s = list(input())
cnt_r = 0
cnt_l = 0
for i in range(n):
	if s[i] == ')':
		cnt_r += 1
	else:
		cnt_l += 1
if cnt_l != cnt_r:
	print(0)
	print(1, 1)
	exit()
pos_r = []
pos_l = []
for i in range(n):
	if s[i] == ')':
		pos_r.append(i)
	else:
		pos_l.append(i)
ans = 0
for i in [0]:
	for j in [0]:
		tmp_ans = 0
		tmp = s[0:]
		(tmp[i], tmp[j]) = (tmp[j], tmp[i])
		cnt = 0
		offset = 0
		min_cnt = 0
		for (num, k) in enumerate(tmp):
			if k == ')':
				cnt -= 1
			else:
				cnt += 1
			if cnt < min_cnt:
				min_cnt = cnt
				offset = num + 1
		cnt = 0
		for (num, k) in enumerate(tmp[offset:] + tmp[0:offset]):
			if k == ')':
				cnt += 1
			else:
				cnt -= 1
			if cnt == 0:
				tmp_ans += 1
		if ans < tmp_ans:
			ans = tmp_ans
			ind1 = i
			ind2 = j
for i in pos_r:
	for j in pos_l:
		tmp_ans = 0
		tmp = s[0:]
		(tmp[i], tmp[j]) = (tmp[j], tmp[i])
		cnt = 0
		offset = 0
		min_cnt = 0
		for (num, k) in enumerate(tmp):
			if k == ')':
				cnt -= 1
			else:
				cnt += 1
			if cnt < min_cnt:
				min_cnt = cnt
				offset = num + 1
		cnt = 0
		for (num, k) in enumerate(tmp[offset:] + tmp[0:offset]):
			if k == ')':
				cnt += 1
			else:
				cnt -= 1
			if cnt == 0:
				tmp_ans += 1
		if ans < tmp_ans:
			ans = tmp_ans
			ind1 = i
			ind2 = j
print(ans)
print(ind1 + 1, ind2 + 1)


n = int(input())
s = list(input())
r = -1
l = n
root = []

def find_right(node):
	global l, r, s, n
	while n:
		r += 1
		n -= 1
		if s[r] == '(':
			node[2].append([r, -1, []])
			find_right(node[2][-1])
		else:
			node[1] = r
			return True
	return False

def find_left(node):
	global l, r, s, n
	while n:
		l -= 1
		n -= 1
		if s[l] == ')':
			node[2].append([-1, l, []])
			find_left(node[2][-1])
		else:
			node[0] = l
			return True
	return False
is_correct = True
while n:
	r += 1
	n -= 1
	if s[r] == '(':
		root.append([r, -1, []])
		is_correct &= find_right(root[-1])
	else:
		root = [[-1, r, root]]
		is_correct &= find_left(root[-1])
sol = [[0, 1, 1]]
if is_correct:
	sol.append([len(root), 1, 1])
	for child in root:
		sol.append([len(child[2]) + 1, child[0] + 1, child[1] + 1])
		for gr_child in child[2]:
			if len(gr_child[2]):
				sol.append([len(root) + len(gr_child[2]) + 1, gr_child[0] + 1, gr_child[1] + 1])
print('%d\n%d %d' % tuple(max(sol)))