This is an easier version of the problem. In this version, $n \le 500$.

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 \leq 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 \ne j$.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 500$), 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 \leq l, r \leq 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.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Complete search

Implementation

Greedy algorithms


Solutions:
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 = 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)


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())
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)))


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 = list(input())
best = 0
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, 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)


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)


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()


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())
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 = [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
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())
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)


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
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())
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)


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))]
		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)
							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())
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())
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)