You are given a bracket sequence $s$ consisting of $n$ opening '(' and closing ')' brackets.

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

You can change the type of some bracket $s_i$. It means that if $s_i = $ ')' then you can change it to '(' and vice versa.

Your task is to calculate the number of positions $i$ such that if you change the type of the $i$-th bracket, then the resulting bracket sequence becomes regular.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 10^6$) — the length of the bracket sequence.

The second line of the input contains the string $s$ consisting of $n$ opening '(' and closing ')' brackets.


-----Output-----

Print one integer — the number of positions $i$ such that if you change the type of the $i$-th bracket, then the resulting bracket sequence becomes regular.


-----Examples-----
Input
6
(((())

Output
3

Input
6
()()()

Output
0

Input
1
)

Output
0

Input
8
)))(((((

Output
0

Difficulty: HARD
Tags: Implementation

Starter code:

Solutions:
def main():
	n = int(input())
	s = ' ' + input()
	a = [0] * (n + 1)
	for i in range(1, n + 1):
		if s[i] == '(':
			a[i] = a[i - 1] + 1
		else:
			a[i] = a[i - 1] - 1
	if a[n] != 2 and a[n] != -2:
		print(0)
		return
	if min(a) < -2:
		print(0)
		return
	if a[n] == 2:
		if min(a) < 0:
			print(0)
			return
		for i in range(n, -1, -1):
			if a[i] == 1:
				print(s[i + 1:].count('('))
				break
	else:
		for i in range(n):
			if a[i] == -1:
				print(s[:i + 1].count(')'))
				break

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
n = int(input())
s = list(input().rstrip())
(c1, c2) = (0, 0)
for i in s:
	if i == '(':
		c1 += 1
	else:
		c2 += 1
if abs(c1 - c2) ^ 2:
	ans = 0
else:
	(x, now) = ([0] * n, 0)
	(ans, m) = (0, n)
	if c1 > c2:
		for i in range(n):
			now += 1 if s[i] == '(' else -1
			x[i] = now
		for i in range(n - 1, -1, -1):
			if s[i] == ')':
				m = min(m, x[i])
			elif 1 < m and 1 < x[i]:
				ans += 1
	else:
		for i in range(n - 1, -1, -1):
			now += 1 if s[i] == ')' else -1
			x[i] = now
		for i in range(n):
			if s[i] == '(':
				m = min(m, x[i])
			elif 1 < m and 1 < x[i]:
				ans += 1
	if min(x) < 0:
		ans = 0
print(ans)


n = int(input())
s = input()
pref = [0] * (n + 1)
suf = [0] * (n + 1)
okp = [0] * (n + 1)
oks = [0] * (n + 1)
okp[0] = 1
oks[n] = 1

def x(i):
	if s[i] == '(':
		return 1
	else:
		return -1

def y(i):
	if s[n - i - 1] == ')':
		return 1
	else:
		return -1
for i in range(n):
	pref[i + 1] = pref[i] + x(i)
	okp[i + 1] = okp[i] & (pref[i + 1] >= 0)
	suf[n - i - 1] = suf[n - i] + y(i)
	oks[n - i - 1] = oks[n - i] & (suf[n - i - 1] >= 0)
ans = 0
for i in range(n):
	if (okp[i] and oks[i + 1]) == 0:
		continue
	if s[i] == '(':
		if pref[i] > 0 and pref[i] - 1 - suf[i + 1] == 0:
			ans += 1
	elif pref[i] + 1 - suf[i + 1] == 0:
		ans += 1
print(ans)


n = int(input())
lis = list(input())
if n % 2:
	print(0)
else:
	st = []
	for i in range(n):
		if lis[i] == ')' and len(st) > 0 and (st[-1] == '('):
			st.pop()
		else:
			st.append(lis[i])
	if len(st) == 2 and st[0] == st[1]:
		if st[0] == '(':
			pre = [0] * (n + 2)
			ans = 0
			for i in range(n):
				if lis[i] == '(':
					pre[i] = pre[i - 1] + 1
				else:
					pre[i] = pre[i - 1] - 1
			c = 0
			for i in range(n - 1, -1, -1):
				if pre[i] <= 1:
					c = i
					break
			for i in range(c + 1, n, 1):
				if pre[i] > pre[i - 1]:
					ans += 1
			print(ans)
		else:
			suf = [0] * (n + 10)
			ans = 0
			for i in range(n - 1, -1, -1):
				if lis[i] == ')':
					suf[i] = suf[i + 1] + 1
				else:
					suf[i] = suf[i + 1] - 1
			c = 0
			for i in range(n):
				if suf[i] <= 1:
					c = i
					break
			for i in range(c):
				if suf[i] > suf[i + 1]:
					ans += 1
			print(ans)
	else:
		print(0)


n = int(input())
s = input().strip()
if n % 2 != 0 or s.startswith(')))') or s.endswith('((('):
	print(0)
	exit(0)
count1 = [0] * n
count2 = [0] * n
S = 0
for i in range(n):
	if s[i] == '(':
		S += 1
	else:
		S -= 1
	if S < 0:
		for j in range(i, n):
			count1[j] = -1
		break
	else:
		count1[i] = S
S = 0
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		S += 1
	else:
		S -= 1
	if S < 0:
		for j in range(i + 1):
			count2[j] = -1
		break
	else:
		count2[i] = S
ans = 0
if n == 2 and (abs(count1[-1]) == 2 or abs(count2[0]) == 2):
	ans += 1
for i in range(1, n - 1):
	if count1[i - 1] >= 0 and count2[i + 1] >= 0:
		if s[i] == '(' and count1[i - 1] == count2[i + 1] + 1:
			ans += 1
		if s[i] == ')' and count1[i - 1] + 1 == count2[i + 1]:
			ans += 1
print(ans)


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

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

def li():
	return list(mi())
n = ii()
s = input().strip()
a = [0] * (n + 1)
m = [0] * (n + 1)
for i in range(n):
	a[i] = a[i - 1] + (1 if s[i] == '(' else -1)
	m[i] = min(m[i - 1], a[i])
ans = 0
mm = a[n - 1]
for j in range(n - 1, -1, -1):
	mm = min(mm, a[j])
	if s[j] == '(':
		if a[n - 1] == 2 and mm == 2 and (m[j - 1] >= 0):
			ans += 1
	elif a[n - 1] == -2 and mm == -2 and (m[j - 1] >= 0):
		ans += 1
print(ans)


def Rd(f=int):
	return [f(x) for x in input().split()]

def PrintFloats(arr):
	return ' '.join(('{:.10f}'.format(x) for x in arr))
n = int(input())
s = input()
op = s.count('(')
cl = s.count(')')

def Solve(s):
	bal = 0
	end = n - 1
	for bwd in range(n - 1, -1, -1):
		if s[bwd] == '(':
			bal += 1
		else:
			bal -= 1
		end = bwd
		if bal > 0:
			break
	bal = 0
	ans = 0
	for fwd in range(n):
		if s[fwd] == '(':
			if bal > 0 and fwd >= end:
				ans += 1
			bal += 1
		else:
			bal -= 1
		if bal < 0:
			break
	return ans
if op == cl + 2:
	print(Solve(s))
elif cl == op + 2:
	s2 = s.replace('(', 'x').replace(')', '(').replace('x', ')')
	print(Solve(s2[::-1]))
else:
	print(0)


n = int(input())
l = list(input())
cptMoins = 0
cptPlus = 0
cpt = 0
dead = False
plusEnd = False
for k in range(n):
	if l[k] == '(':
		cpt += 1
		cptMoins += 1
	else:
		cpt -= 1
		if not plusEnd:
			cptPlus += 1
	if cpt < -2:
		dead = True
		break
	if cpt < 0:
		if plusEnd or cptPlus == 0:
			dead = True
			break
		else:
			plusEnd = True
			cpt += 2
	if cpt < 2:
		cptMoins = 0
if dead:
	print(0)
elif plusEnd and cpt == 0:
	print(cptPlus)
elif not plusEnd and cpt == 2:
	print(cptMoins)
else:
	print(0)


def main():
	count = int(input())
	string = input()
	front = [0]
	back = [0]
	for x in range(count):
		if string[x] == '(':
			front.append(front[-1] + 1)
		else:
			front.append(front[-1] - 1)
	for x in range(count - 1, -1, -1):
		if string[x] == ')':
			back.append(back[-1] + 1)
		else:
			back.append(back[-1] - 1)
	assert back[-1] == -front[-1]
	valid_front = [False for x in range(count + 1)]
	valid_back = [False for x in range(count + 1)]
	for x in range(count + 1):
		if front[x] >= 0:
			valid_front[x] = True
		else:
			break
	for x in range(count + 1):
		if back[x] >= 0:
			valid_back[x] = True
		else:
			break
	tot = 0
	for x in range(count):
		if valid_front[x] and valid_back[count - x - 1]:
			if string[x] == ')':
				if front[x] + 1 - back[count - x - 1] == 0:
					tot += 1
			elif front[x] - 1 - back[count - x - 1] == 0:
				tot += 1
	print(tot)
main()


n = int(input())
s = input()
r = [(0, 0)] * (n + 1)
opening = 0
r1 = 0
for i in range(n):
	if s[i] == '(':
		opening += 1
	elif opening > 0:
		r1 += 2
		opening -= 1
	r[i + 1] = (opening, r1)
closing = 0
l = [(0, 0)] * (n + 1)
r1 = 0
for i in range(n - 1, 0, -1):
	if s[i] == ')':
		closing += 1
	elif closing > 0:
		r1 += 2
		closing -= 1
	l[i - 1] = (closing, r1)
if abs(s.count(')') - s.count('(')) != 2:
	print(0)
	exit()
ans = 0
for i in range(n):
	if abs(r[i][0] - l[i][0]) == 1 and r[i][0] + l[i][0] + r[i][1] + l[i][1] == n - 1:
		ans += 1
print(ans)


def case1(s: str, n: int):
	val = 0
	count = 0
	for i in range(n):
		if s[i] == '(':
			val += 1
		else:
			val -= 1
		if val < 0:
			return 0
		elif val == 0 or val == 1:
			count = 0
		elif s[i] == '(':
			count += 1
	return count

def case2(s: str, n: int):
	val = 0
	count = 0
	for i in range(n):
		if s[i] == '(':
			val += 1
		else:
			val -= 1
		if val == -1:
			val += 2
			for j in range(i + 1, n):
				if s[j] == '(':
					val += 1
				else:
					val -= 1
				if val < 0:
					return 0
			return count + 1
		elif s[i] == ')':
			count += 1
	return count
n = int(input())
s = input()
l = 0
r = 0
for i in range(n):
	if s[i] == '(':
		l += 1
	else:
		r += 1
if l - r == 2:
	print(case1(s, n))
elif l - r == -2:
	print(case2(s, n))
else:
	print(0)


from sys import stdout, stdin
import math
n = int(input())
s = input()
zuor = {'(': 1, ')': -1}
arr = [zuor[c] for c in s]
obpos = [z == 1 for z in arr]
(suma, sume) = ([], [])
akt = 0
for z in arr:
	akt += z
	suma.append(akt)
akt = 0
for z in reversed(arr):
	akt -= z
	sume.append(akt)
sume = list(reversed(sume))
summe = sum(arr)
if min(suma) < -2 or min(sume) < -2:
	print(0)
elif summe == 2:
	if min(suma) < 0:
		print(0)
	else:
		letzte1 = len(suma) - 1 - suma[::-1].index(1)
		ok = [i > letzte1 for i in range(n)]
		print(sum((b1 and b2 for (b1, b2) in zip(ok, obpos))))
elif summe == -2:
	if min(sume) < 0:
		print(0)
	else:
		erste1 = sume.index(1)
		ok = [i < erste1 for i in range(n)]
		print(sum((b1 and (not b2) for (b1, b2) in zip(ok, obpos))))
else:
	print(0)


n = int(input())
a = list(input())
k = 0
st = []
for i in range(n):
	if a[i] == ')' and len(st) > 0 and (st[-1][0] == '('):
		k += 2
		st.pop()
	else:
		st.append([a[i], i + 1])
if n % 2 == 1 or len(st) == 0:
	print(0)
elif len(st) == 2 and st[0][0] == st[1][0]:
	if st[0][0] == '(':
		print((n - st[1][1]) // 2 + 1)
	else:
		print(st[0][1] // 2 + 1)
else:
	print(0)


import sys, os
from math import sqrt, gcd, ceil, log, floor
from math import factorial as fact
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
MOD = 10 ** 9 + 7

def main():
	n = int(input())
	s = input().strip()
	if n % 2:
		print(0)
		exit()
	pref = [0] * n
	suf = [0] * n
	invalidpref = [0] * n
	invalidsuf = [0] * n
	pref[0] = [1, -1][s[0] == ')']
	suf[-1] = [1, -1][s[-1] == '(']
	invalidpref[0] = s[0] == ')'
	invalidsuf[-1] = s[-1] == '('
	for i in range(1, n):
		pref[i] = pref[i - 1] + [1, -1][s[i] == ')']
		suf[n - i - 1] = suf[n - i] + [1, -1][s[n - i - 1] == '(']
		invalidpref[i] = invalidpref[i - 1] | (pref[i] < 0)
		invalidsuf[n - i - 1] = invalidsuf[n - i] | (suf[n - i - 1] < 0)
	ans = 0
	if s[0] == ')' and (not invalidsuf[0]):
		ans += 1 - suf[1] == 0
	if s[-1] == '(' and (not invalidpref[-1]):
		ans += pref[-2] - 1 == 0
	for i in range(1, n - 1):
		if invalidpref[i - 1] or invalidsuf[i + 1]:
			continue
		elif s[i] == ')' and pref[i - 1] + 1 - suf[i + 1] == 0:
			ans += 1
		elif s[i] == '(' and pref[i - 1] - 1 - suf[i + 1] == 0:
			ans += 1
	print(ans)
main()


n = int(input())
s = input().strip()
a = [0] * (n + 5)
a2 = [0] * (n + 5)
mn = [0] * (n + 5)
mn2 = [0] * (n + 5)
for i in range(1, n + 1, 1):
	if s[i - 1] == '(':
		a[i] = a[i - 1] + 1
	else:
		a[i] = a[i - 1] - 1
	mn[i] = min(mn[i - 1], a[i])
for i in range(n, 0, -1):
	if s[i - 1] == ')':
		a2[i] = a2[i + 1] + 1
	else:
		a2[i] = a2[i + 1] - 1
	mn2[i] = min(mn2[i + 1], a2[i])
ans = 0
if a[n] != 2 and a[n] != -2:
	print(0)
	return
for i in range(1, n + 1, 1):
	if s[i - 1] == '(' and a[n] == 2:
		if mn[i - 1] >= 0 and mn2[i + 1] >= 0 and (a[i - 1] >= 1):
			ans = ans + 1
	elif s[i - 1] == ')' and a[n] == -2:
		if mn[i - 1] >= 0 and mn2[i + 1] >= 0 and (a2[i + 1] >= 1):
			ans = ans + 1
print(ans)


n = int(input())
s = input()
ans = 0
(s1, s2) = ([], [])
f1 = [1] * n
f2 = [1] * n
for i in range(n):
	s1.append([0, 0])
	s2.append([0, 0])
if s[0] == '(':
	s1[0][0] += 1
else:
	s1[0][1] += 1
for i in range(1, n):
	s1[i][0] = s1[i - 1][0]
	s1[i][1] = s1[i - 1][1]
	if s[i] == '(':
		s1[i][0] += 1
	else:
		s1[i][1] += 1
if s[-1] == '(':
	s2[-1][0] += 1
else:
	s2[-1][1] += 1
for i in range(n - 2, -1, -1):
	s2[i][0] = s2[i + 1][0]
	s2[i][1] = s2[i + 1][1]
	if s[i] == '(':
		s2[i][0] += 1
	else:
		s2[i][1] += 1
if s[0] == ')':
	f1[0] = 0
for i in range(1, n):
	if f1[i - 1] == 1 and s1[i][1] <= s1[i][0]:
		f1[i] = 1
	else:
		f1[i] = 0
if s[-1] == '(':
	f2[-1] = 0
for i in range(n - 2, -1, -1):
	if f2[i + 1] == 1 and s2[i][0] <= s2[i][1]:
		f2[i] = 1
	else:
		f2[i] = 0
for i in range(n):
	t1 = s1[-1][0]
	t2 = s1[-1][1]
	if i % 2 == 1:
		if i + 1 < n:
			p1 = s2[i + 1][0]
			p2 = s2[i + 1][1]
			if p1 > p2 or f2[i + 1] == 0:
				continue
		p1 = s1[i][0]
		p2 = s1[i][1]
		q1 = s2[i][0]
		q2 = s2[i][1]
		if s[i] == '(':
			p1 -= 1
			p2 += 1
			t1 -= 1
			t2 += 1
			q1 -= 1
			q2 += 1
		else:
			p2 -= 1
			p1 += 1
			t1 += 1
			t2 -= 1
			q2 -= 1
			q1 += 1
		if p2 > p1:
			continue
		if q1 > q2:
			continue
		if i - 1 >= 0 and f1[i - 1] == 0:
			continue
		if t1 == t2:
			ans += 1
	else:
		if i - 1 >= 0:
			p1 = s1[i - 1][0]
			p2 = s1[i - 1][1]
			if p2 > p1 or f1[i - 1] == 0:
				continue
		p1 = s2[i][0]
		p2 = s2[i][1]
		q1 = s1[i][0]
		q2 = s1[i][1]
		if s[i] == '(':
			p1 -= 1
			p2 += 1
			t1 -= 1
			t2 += 1
			q1 -= 1
			q2 += 1
		else:
			p1 += 1
			p2 -= 1
			t1 += 1
			t2 -= 1
			q1 += 1
			q2 -= 1
		if p2 < p1:
			continue
		if q1 < q2:
			continue
		if i + 1 < n and f2[i + 1] == 0:
			continue
		if t1 == t2:
			ans += 1
print(ans)


n = int(input())
s = input()
open = s.count('(')
close = s.count(')')
counter = 0
for i in range(n):
	if s[i] == '(':
		counter += 1
	else:
		counter -= 1
	if counter <= -3:
		print(0)
		exit()
if open - close == 2:
	ans = 0
	ansFound = False
	for i in reversed(range(n)):
		if s[i] == '(':
			if not ansFound:
				ans += 1
			if counter <= 2:
				ansFound = True
			counter -= 1
		else:
			counter += 1
		if counter < 0:
			print(0)
			exit()
	print(ans)
elif close - open == 2:
	counter = 0
	ans = 0
	for i in range(n):
		if s[i] == '(':
			counter += 1
		else:
			counter -= 1
			ans += 1
		if counter < 0:
			break
	print(ans)
else:
	print(0)


n = int(input())
s = input()
o = 0
c = 0
n = len(s)
for i in range(n):
	if s[i] == '(':
		o += 1
	else:
		c += 1
if n % 2 != 0:
	print(0)
	quit()
if abs(o - c) > 2:
	print(0)
	quit()
t = 0
count = 0
ans = 0
for i in range(n):
	if s[i] == '(':
		count += 1
	else:
		count -= 1
	if count < -2:
		t = 1
if t == 1:
	print(0)
	quit()
ind = n - 1
count = 0
if o > c:
	ind = -1
	for i in range(n):
		if s[i] == '(':
			count += 1
		else:
			count -= 1
		if count < 0:
			print(0)
			quit()
		if count < 2:
			ind = i
	for i in range(ind + 1, n):
		if count > 0 and s[i] == '(':
			ans += 1
		if s[i] == '(':
			count += 1
		else:
			count -= 1
		if count < 0:
			t = 1
elif c > o:
	for i in range(n):
		if s[i] == '(':
			count += 1
		else:
			count -= 1
		if count < 0:
			ind = i
			break
	for i in range(ind + 1):
		if s[i] == ')':
			ans += 1
else:
	print(0)
	quit()
print(ans)


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

def sol(n, S):
	L = [0]
	for s in S:
		if s == '(':
			L.append(L[-1] + 1)
		else:
			L.append(L[-1] - 1)
	ANS = 0
	L = L[1:]
	if L[-1] == 2:
		if min(L) < 0:
			return 0
		for j in range(n - 1, -1, -1):
			if L[j] < 2:
				break
		for k in range(j + 1, n, 1):
			if S[k] == '(':
				ANS += 1
	elif L[-1] == -2:
		if min(L) < -2:
			return 0
		for j in range(n):
			if L[j] < 0:
				break
		for k in range(j, -1, -1):
			if S[k] == ')':
				ANS += 1
	else:
		ANS = 0
	return ANS
print(sol(n, s))


n = int(input())
s = input()
(diff, cura, curb) = ([], 0, 0)
for item in s:
	if item == '(':
		cura += 1
	else:
		curb += 1
	diff.append(cura - curb)
if diff[-1] == 2:
	if min(diff) < 0:
		print(0)
	else:
		(ans, i) = (0, n - 1)
		while i >= 0 and diff[i] >= 2:
			if s[i] == '(':
				ans += 1
			i -= 1
		print(ans)
elif diff[-1] == -2:
	if min(diff) < -2:
		print(0)
	else:
		ans = 0
		for i in range(0, n - 1):
			if s[i] == ')' and diff[i] >= 0:
				ans += 1
			elif diff[i] < 0:
				if s[i] == ')':
					ans += 1
				break
		print(ans)
else:
	print(0)


import sys
import bisect
from random import randint
input = lambda : sys.stdin.readline().strip('\r\n')
from math import gcd
sa = lambda : input()
sb = lambda : int(input())
sc = lambda : input().split()
sd = lambda : list(map(int, input().split()))
se = lambda : float(input())
sf = lambda : list(input())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def hnbhai():
	n = sb()
	s = sa()
	a = []
	for i in range(n):
		if s[i] == ')' and len(a) > 0 and (a[-1][0] == '('):
			a.pop()
		else:
			a.append([s[i], i + 1])
	if n % 2 or len(a) == 0:
		print(0)
		return
	if len(a) == 2 and a[0][0] == a[1][0]:
		if a[0][0] == '(':
			print((n - a[1][1]) // 2 + 1)
		else:
			print(a[0][1] // 2 + 1)
		return
	print(0)
for _ in range(1):
	hnbhai()


import sys
n = int(sys.stdin.readline())
s = sys.stdin.readline()[:-1]
pre = [0 for _ in range(n + 2)]
suf = [0 for _ in range(n + 2)]
for i in range(1, n + 1):
	if s[i - 1] == ')':
		if pre[i - 1] == 0:
			pre[i] = float('inf')
		else:
			pre[i] = pre[i - 1] - 1
	else:
		pre[i] = pre[i - 1] + 1
for i in range(n, 0, -1):
	if s[i - 1] == '(':
		if suf[i + 1] == 0:
			suf[i] = float('inf')
		else:
			suf[i] = suf[i + 1] + 1
	else:
		suf[i] = suf[i + 1] - 1
ans = 0
for i in range(1, n + 1):
	if s[i - 1] == ')':
		x = pre[i - 1]
		y = suf[i + 1]
		if x + y + 1 == 0:
			ans += 1
	else:
		x = pre[i - 1]
		y = suf[i + 1]
		if x + y - 1 == 0:
			ans += 1
print(ans)


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=-10 ** 6, 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(50001)]
pp = []

def SieveOfEratosthenes(n=50000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(50001):
		if prime[i]:
			pp.append(i)
n = int(input())
s = input()
pre = [[0, 0] for i in range(n)]
post = [[0, 0] for i in range(n)]
curr = 0
ch = 1
for i in range(n):
	pre[i][0] = curr
	pre[i][1] = ch
	if s[i] == '(':
		curr += 1
	else:
		curr -= 1
	if curr < 0:
		ch = 0
curr = 0
ch = 1
for i in range(n - 1, -1, -1):
	post[i][0] = curr
	post[i][1] = ch
	if s[i] == '(':
		curr += 1
	else:
		curr -= 1
	if curr > 0:
		ch = 0
count = 0
for i in range(n):
	if pre[i][1] == 0 or post[i][1] == 0:
		continue
	if s[i] == '(':
		d = -1
	else:
		d = 1
	if pre[i][0] + d >= 0 and pre[i][0] + d + post[i][0] == 0:
		count += 1
print(count)


from sys import stdin, stdout
import collections
import math
N = int(input())
s = input()
level = 0
L = [0] * N
for i in range(N):
	if s[i] == '(':
		level += 1
	else:
		level -= 1
	L[i] = level
if level != 2 and level != -2:
	print(0)
	quit()
mini = level
res = 0
if level == 2:
	last = [0] * N
	front = [0] * N
	for i in range(N - 1, -1, -1):
		mini = min(mini, L[i])
		last[i] = mini
	mini = L[0]
	for i in range(N):
		mini = min(mini, L[i])
		front[i] = mini
	for i in range(N):
		if front[i] >= 0 and last[i] >= 2 and (s[i] == '('):
			res += 1
if level == -2:
	last = [0] * N
	front = [0] * N
	for i in range(N - 1, -1, -1):
		mini = min(mini, L[i])
		last[i] = mini
	mini = 0
	for i in range(N):
		front[i] = mini
		mini = min(mini, L[i])
	for i in range(N):
		if front[i] >= 0 and last[i] >= -2 and (s[i] == ')'):
			res += 1
print(res)


input()
line = input()
wasm = -1
last0 = 0
last1 = -1
curs = 0
err = False
for i in range(len(line)):
	if line[i] == '(':
		curs += 1
	else:
		curs -= 1
	if curs == 0:
		last0 = i
	if curs == 1:
		last1 = i
	if curs < 0:
		if wasm == -1:
			wasm = i
		if curs < -2:
			err = True
			break
if err:
	print(0)
elif wasm == -1:
	if curs != 2:
		print(0)
	else:
		print(int((len(line) - max(last0, last1)) / 2))
elif curs != -2:
	print(0)
else:
	print(int(wasm / 2) + 1)


n = int(input())
s = input().strip()
if n % 2 != 0 or s[:3] == ')))' or s[-3:] == '(((':
	print(0)
	exit()
if s == '((' or s == '))':
	print(1)
	exit()
count1 = [0] * n
flag1 = False
count2 = [0] * n
flag2 = False
S = 0
for i in range(n):
	if s[i] == '(':
		S += 1
	else:
		S -= 1
	if S < 0:
		flag1 = True
		for j in range(i, n):
			count1[j] = -1
		break
	else:
		count1[i] = S
S = 0
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		S += 1
	else:
		S -= 1
	if S < 0:
		flag2 = True
		for j in range(i + 1):
			count2[j] = -1
		break
	else:
		count2[i] = S
if count2[0] == 2 and count2[2] == 0 and (not flag2) or (count1[-1] == 2 and count1[-3] == 0 and (not flag1)):
	print(1)
	exit()
ans = 0
for i in range(1, n - 1):
	if count1[i - 1] >= 0 and count2[i + 1] >= 0:
		if s[i] == '(' and count1[i - 1] == count2[i + 1] + 1:
			ans += 1
		if s[i] == ')' and count1[i - 1] + 1 == count2[i + 1]:
			ans += 1
print(ans)


n = int(input())
s = list(input())
stk = []
for i in range(n):
	if s[i] == ')' and len(stk) > 0 and (stk[-1][0] == '('):
		stk.pop()
	else:
		stk.append([s[i], i + 1])
if len(stk) == 2 and stk[0][0] == stk[1][0]:
	if stk[0][0] == '(':
		print((n - stk[1][1]) // 2 + 1)
	else:
		print(stk[0][1] // 2 + 1)
else:
	print(0)


import sys
import math
data = sys.stdin.read().split()
data_ptr = 0

def data_next():
	global data_ptr, data
	data_ptr += 1
	return data[data_ptr - 1]
N = int(data_next())
S = list(data[1])
n_open = S.count('(')
n_closed = N - n_open
if n_open > n_closed:
	S.reverse()
	for i in range(N):
		if S[i] == '(':
			S[i] = ')'
		else:
			S[i] = '('
depth = 0
ans = 0
past_first_neg = False
for i in range(N):
	if S[i] == ')':
		depth -= 1
		if depth < -2:
			ans = 0
			break
		if not past_first_neg:
			ans += 1
		if depth < 0:
			past_first_neg = True
	else:
		depth += 1
if depth != -2:
	ans = 0
print(ans)


_ = input()
s = list(input())

def regular(s):
	k = 0
	for c in s:
		if c == '(':
			k += 1
		elif c == ')':
			k -= 1
		if k < 0:
			return False
	return k == 0

def regular_sums(s):
	k = 0
	ks = []
	for c in s:
		if c == '(':
			k += 1
		elif c == ')':
			k -= 1
		ks.append(k)
	return ks
sums = regular_sums(s)
if sums[-1] == 2:
	ia = 0
	while ia < len(sums) and sums[ia] >= 0:
		ia += 1
	ib = len(s) - 1
	while ib >= 0 and sums[ib] >= 2:
		ib -= 1
	k = 0
	for i in range(max(ib + 1, 0), min(ia + 1, len(s))):
		if s[i] == '(':
			k += 1
	print(k)
elif sums[-1] == -2:
	ia = 0
	while ia < len(sums) and sums[ia] >= 0:
		ia += 1
	ib = len(s) - 1
	while ib >= 0 and sums[ib] >= -2:
		ib -= 1
	k = 0
	for i in range(max(ib + 1, 0), min(ia + 1, len(s))):
		if s[i] == ')':
			k += 1
	print(k)
else:
	print(0)


n = int(input())
s = input()
f = 0
b = 0
l = []
for i in range(n):
	l.append(f - b)
	if s[i] == '(':
		f = f + 1
	else:
		b = b + 1
f = 0
b = 0
r = []
for i in range(n - 1, -1, -1):
	r.append(b - f)
	if s[i] == '(':
		f = f + 1
	else:
		b = b + 1
r = r[::-1]
fl = [False] * n
i = 0
while i < n:
	if l[i] < 0:
		break
	i = i + 1
for j in range(i + 1, n):
	fl[j] = True
fr = [False] * n
i = n - 1
while i >= 0:
	if r[i] < 0:
		break
	i = i - 1
for j in range(i - 1, -1, -1):
	fr[j] = True
cnt = 0
for i in range(n):
	if s[i] == '(':
		if l[i] - r[i] == 1 and l[i] > 0 and (r[i] >= 0) and (fl[i] == False) and (fr[i] == False):
			cnt = cnt + 1
	elif r[i] - l[i] == 1 and r[i] > 0 and (l[i] >= 0) and (fl[i] == False) and (fr[i] == False):
		cnt = cnt + 1
print(cnt)


inf = 10 ** 6 + 10

def main():
	n = int(input())
	a = list(input())
	dif = [0] * n
	s = 0
	ldif = [inf] * (n + 1)
	rdif = [inf] * (n + 1)
	for i in range(n):
		if a[i] == '(':
			s += 1
		else:
			s -= 1
		dif[i] = s
		ldif[i] = min(ldif[i - 1], s)
	for i in range(n):
		rdif[n - 1 - i] = min(rdif[n - i], dif[-(i + 1)])
	ans = 0
	if abs(dif[-1]) != 2:
		print(0)
		return
	elif dif[-1] == 2:
		for i in range(n):
			if a[i] == '(' and ldif[i - 1] >= 0 and (rdif[i] >= 2):
				ans += 1
		print(ans)
		return
	elif dif[-1] == -2:
		for i in range(n):
			if a[i] == ')' and ldif[i - 1] >= 0 and (rdif[i] >= -2):
				ans += 1
		print(ans)
		return
main()


in1 = int(input())
in2 = input()
count = 0
series = []
if in1 == 1:
	print(0)
else:
	for x in in2:
		if x == '(':
			series.append(1)
		else:
			series.append(-1)
	for x in range(len(series) - 1):
		series[x + 1] = series[x] + series[x + 1]
	if series[-1] == 2 and min(series) >= 0:
		count = 0
		for x in range(1, len(series)):
			if series[-x] >= 2:
				if in2[-x] == '(':
					count += 1
			else:
				break
	elif series[-1] == -2 and min(series) >= -2:
		count = 0
		for x in range(len(series)):
			if in2[x] == ')':
				count += 1
			if series[x] < 0:
				break
	print(count)


n = int(input())
sequence = input()
moreopen = 0
moreclosed = 0
small = 0
stack = 0
stop = False
completestop = False
for i in range(n):
	if sequence[i] == '(':
		stack += 1
	else:
		stack -= 1
	if stack >= 2 and sequence[i] == '(':
		moreopen += 1
	if stack <= 1:
		moreopen = 0
	if stack >= -2 and (not stop) and (sequence[i] == ')'):
		moreclosed += 1
	if stack < 0:
		stop = True
	if stack < -2:
		completestop = True
		break
if completestop:
	print(0)
elif stack == 2 and (not stop):
	print(moreopen)
elif stack == -2:
	print(moreclosed)
else:
	print(0)


from sys import stdin
n = int(stdin.readline().strip())
s = input()
if n == 1:
	print(0)
	exit(0)
dp1 = [0 for i in range(n)]
dp2 = [0 for i in range(n)]
v1 = [True for i in range(n)]
v2 = [True for i in range(n)]
for i in range(n):
	if s[i] == '(':
		dp1[i] = dp1[i - 1] + 1
	else:
		dp1[i] = dp1[i - 1] - 1
if s[n - 1] == '(':
	dp2[n - 1] = 1
else:
	dp2[n - 1] = -1
for i in range(n - 2, -1, -1):
	if s[i] == '(':
		dp2[i] = dp2[i + 1] + 1
	else:
		dp2[i] = dp2[i + 1] - 1
for i in range(n):
	if dp1[i] < 0:
		v1[i] = False
	if i > 0 and v1[i - 1] == False:
		v1[i] = False
for i in range(n - 1, -1, -1):
	if dp2[i] > 0:
		v2[i] = False
	if i <= n - 2 and v2[i + 1] == False:
		v2[i] = False
ans = 0
for i in range(1, n - 1):
	if s[i] == '(':
		if dp1[i - 1] - 1 + dp2[i + 1] == 0 and v1[i - 1] and v2[i + 1]:
			ans += 1
	elif dp1[i - 1] + 1 + dp2[i + 1] == 0 and v1[i - 1] and v2[i + 1]:
		ans += 1
if s[0] == ')' and dp2[1] == -1 and v2[1]:
	ans += 1
if s[n - 1] == '(' and dp1[n - 2] == 1 and v1[n - 2]:
	ans += 1
print(ans)


n = int(input())
str = input()
balance = 0
for x in str:
	if x == '(':
		balance += 1
	else:
		balance -= 1
pre = []
pre_balance = 0
for x in str:
	if x == '(':
		pre_balance += 1
	else:
		pre_balance -= 1
	pre.append(pre_balance)
suf = []
lowest = []
suf_balance = 0
high = 0
low = 0
for x in reversed(str):
	suf.append(suf_balance)
	high = max(high, suf_balance)
	low = suf_balance - high
	lowest.append(low)
	if x == '(':
		suf_balance += 1
	else:
		suf_balance -= 1
suf.reverse()
lowest.reverse()
ans = 0
if balance == 2:
	is_bad = False
	for (i, x) in enumerate(str):
		if is_bad:
			break
		if x == '(':
			new_pre = pre[i] - 2
			if new_pre >= 0 and new_pre == -suf[i] and (new_pre >= -lowest[i]):
				if i + 1 == n or str[-1] != '(':
					ans += 1
		if pre[i] < 0:
			is_bad = True
elif balance == -2:
	is_bad = False
	for (i, x) in enumerate(str):
		if is_bad:
			break
		if x == ')':
			new_pre = pre[i] + 2
			if new_pre >= 0 and new_pre == -suf[i] and (new_pre >= -lowest[i]):
				if i + 1 == n or str[-1] != '(':
					ans += 1
		if pre[i] < 0:
			is_bad = True
print(ans)


(n, ls) = (int(input()), [1 if x == '(' else -1 for x in input()])
op = sum(ls)
if n & 1 or op > 2 or op < -2 or (op == 0):
	print(0)
	raise SystemExit()
runningsum = 0
cd = False
poss = 0
if op > 0:
	for i in range(n):
		runningsum += ls[i]
		if runningsum > 1 and ls[i] == 1:
			poss += 1
		if runningsum < 2:
			poss = 0
		if runningsum < 0:
			print(0)
			raise SystemExit()
else:
	for i in range(n - 1, -1, -1):
		runningsum -= ls[i]
		if runningsum > 1 and ls[i] == -1:
			poss += 1
		if runningsum < 2:
			poss = 0
		if runningsum < 0:
			print(0)
			raise SystemExit()
print(poss)


n = int(input())
s = input()
nums = []
for ch in s:
	if ch == '(':
		nums.append(1)
	else:
		nums.append(-1)
for i in range(1, n):
	nums[i] += nums[i - 1]
if nums[-1] == 2 and all((i >= 0 for i in nums)):
	ans = 0
	for i in range(n - 1, -1, -1):
		if nums[i] < 2:
			break
		if s[i] == '(':
			ans += 1
	print(ans)
elif nums[-1] == -2 and min(nums) == -2:
	ans = 0
	for i in range(n):
		if s[i] == ')':
			ans += 1
		if nums[i] < 0:
			break
	print(ans)
else:
	print(0)


(n, s, x, k, l) = (int(input()), input(), 0, 0, [])
for i in range(n):
	if s[i] == '(':
		l.append(i)
	elif not l:
		x += 1
		if x == 1:
			k = i
	else:
		l.pop()
print((n - l[-1]) // 2 + 1 if x == 0 and len(l) == 2 else k // 2 + 1 if not l and x == 2 else 0)


for _ in range(1):
	n = int(input())
	st = list(input().strip())
	rt = st[:]
	count = 0
	add = 0
	store_f = -1
	store_b = -1
	if n % 2 == 1:
		print(0)
		continue
	for i in range(n):
		if st[i] == '(':
			add += 1
			continue
		add -= 1
		if add < 0:
			count += 1
			add += 2
			st[i] = '('
			store_f = i
	sub = 0
	for i in range(n - 1, -1, -1):
		if st[i] == ')':
			sub += 1
			continue
		sub -= 1
		if sub < 0:
			count += 1
			sub += 2
			st[i] = ')'
			store_b = i
	if count >= 2 or count == 0:
		print(0)
		continue
	if count == 1 and (add == 0 and sub == 0 or (add == 2 and sub == 0)):
		if store_b == -1:
			print(rt[:store_f + 1].count(')'))
		else:
			print(rt[store_b:].count('('))


def E():
	n = int(input())
	brackets = input()
	if n % 2:
		print(0)
		return
	cumm_brackets = []
	for b in brackets:
		if not len(cumm_brackets):
			cumm_brackets.append(1 if b == '(' else -1)
		else:
			cumm_brackets.append(cumm_brackets[-1] + 1 if b == '(' else cumm_brackets[-1] - 1)
	if abs(cumm_brackets[-1]) != 2:
		print(0)
		return
	if cumm_brackets[-1] == 2:
		if -1 in cumm_brackets:
			print(0)
			return
		last_under_2_index = 0
		for i in range(n - 1):
			if cumm_brackets[i] < 2:
				last_under_2_index = i
		answer = 0
		for i in range(last_under_2_index + 1, n):
			if brackets[i] == '(':
				answer += 1
	if cumm_brackets[-1] == -2:
		if min(cumm_brackets) <= -3:
			print(0)
			return
		for first_under_minus_2_index in range(n):
			if cumm_brackets[first_under_minus_2_index] == -1:
				break
		answer = 0
		for i in range(first_under_minus_2_index + 1):
			if brackets[i] == ')':
				answer += 1
	print(answer)
E()


n = int(input())
s = input()
prefBal = [0] * n
prefBal.append(0)
prefCan = [False] * n
prefCan.append(True)
suffBal = [0] * n
suffBal.append(0)
suffCan = [False] * n
suffCan.append(True)
currBal = 0
currCan = True
for i in range(n):
	if s[i] == '(':
		prefBal[i] = currBal + 1
	else:
		prefBal[i] = currBal - 1
	currBal = prefBal[i]
	prefCan[i] = currCan and prefBal[i] >= 0
	currCan = prefCan[i]
currBal = 0
currCan = True
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		suffBal[i] = currBal + 1
	else:
		suffBal[i] = currBal - 1
	currBal = suffBal[i]
	suffCan[i] = currCan and suffBal[i] >= 0
	currCan = suffCan[i]
ans = 0
for i in range(n):
	if s[i] == '(':
		if prefCan[i - 1] and suffCan[i + 1] and (prefBal[i - 1] - 1 - suffBal[i + 1] == 0):
			ans += 1
	if s[i] == ')':
		if prefCan[i - 1] and suffCan[i + 1] and (prefBal[i - 1] + 1 - suffBal[i + 1] == 0):
			ans += 1
print(ans)


n = int(input())
s = input().strip()
a = [0] * (n + 1)
m = [0] * (n + 1)
for i in range(n):
	a[i] = a[i - 1] + (1 if s[i] == '(' else -1)
	m[i] = min(m[i - 1], a[i])
ans = 0
mm = a[n - 1]
for j in range(n - 1, -1, -1):
	mm = min(mm, a[j])
	if s[j] == '(':
		ans += a[n - 1] == 2 and mm == 2 and (m[j - 1] >= 0)
	else:
		ans += a[n - 1] == -2 and mm == -2 and (m[j - 1] >= 0)
print(ans)


def read(type=1):
	if type:
		file = open('input.dat', 'r')
		n = int(file.readline())
		a = file.readline()
		file.close()
	else:
		n = int(input().strip())
		a = input().strip()
	return (n, a)

def solve():
	sol = 0
	vs = []
	v = 0
	for i in range(n):
		if a[i] == '(':
			v += 1
		else:
			v -= 1
		vs.append(v)
	mins = [10000000 for i in range(n)]
	last = n
	for i in range(n):
		if i:
			mins[n - i - 1] = min(vs[n - i - 1], mins[n - i])
		else:
			mins[n - i - 1] = vs[n - i - 1]
		if vs[n - i - 1] < 0:
			last = n - i - 1
	for i in range(n):
		if a[i] == '(' and vs[n - 1] == 2:
			if i:
				if mins[i] >= 2:
					sol += 1
		if a[i] == ')' and vs[n - 1] == -2:
			if i != n - 1:
				if mins[i] >= -2:
					sol += 1
		if i == last:
			break
	return sol
(n, a) = read(0)
sol = solve()
print(sol)


n = int(input())
xs = list(map(lambda x: 1 if x == '(' else -1, list(input())))
head = [0 for _ in range(0, n + 1)]
tail = [0 for _ in range(0, n + 1)]
head[0] = xs[0]
for i in range(1, n):
	head[i] = head[i - 1] + xs[i]
tail[n] = 0
for i in range(n - 1, 0, -1):
	tail[i] = tail[i + 1] + xs[i]
a = 0
for x in head[:-1]:
	a += 1
	if x < 0:
		break
b = 0
for x in reversed(tail[:-1]):
	b += 1
	if x > 0:
		break
ans = 0
for i in range(len(xs) - b, a):
	diff = 2 if xs[i] < 0 else -2
	if head[i] + diff >= 0 and head[i] + diff + tail[i + 1] == 0:
		ans += 1
print(ans)


import sys

def solve(io):
	N = io.read_int()
	S = io.read_line()
	delta = [0] * (N + 1)
	for i in range(0, N):
		if S[i] == '(':
			delta[i + 1] = delta[i] + 1
		else:
			delta[i + 1] = delta[i] - 1
	minDelta = [0] * (N + 1)
	minDelta[-1] = delta[-1]
	for i in range(N - 1, -1, -1):
		minDelta[i] = min(delta[i], minDelta[i + 1])
	cnt = 0
	for i in range(0, N):
		if S[i] == '(':
			if delta[-1] == 2 and minDelta[i + 1] >= 2:
				cnt += 1
		elif delta[-1] == -2 and minDelta[i + 1] >= -2:
			cnt += 1
		if delta[i + 1] < 0:
			break
	io.println(cnt)

class IO:
	in_stream = None
	out_stream = None
	raw = ''
	buf = []
	pos = 0

	def __init__(self, input_stream, output_stream):
		self.in_stream = input_stream
		self.out_stream = output_stream

	def read_to_buffer(self):
		self.raw = self.in_stream.readline().rstrip('\n')
		self.buf = self.raw.split()
		self.pos = 0

	def read_string(self):
		while self.pos == len(self.buf):
			self.read_to_buffer()
		ans = self.buf[self.pos]
		self.pos += 1
		return ans

	def read_int(self):
		return int(self.read_string())

	def read_float(self):
		return float(self.read_string())

	def read_string_array(self, N, offset=0):
		arr = [None] * offset
		for _ in range(0, N):
			arr.append(self.read_string())
		return arr

	def read_int_array(self, N, offset=0):
		arr = [None] * offset
		for _ in range(0, N):
			arr.append(self.read_int())
		return arr

	def read_float_array(self, N, offset=0):
		arr = [None] * offset
		for _ in range(0, N):
			arr.append(self.read_float())
		return arr

	def read_line(self):
		while self.pos == len(self.buf):
			self.read_to_buffer()
		if self.pos > 0:
			raise ValueError('Cannot call read_line in the middle of a line.')
		self.pos = len(self.buf)
		return self.raw

	def print(self, *args):
		self.out_stream.write(' '.join([str(x) for x in args]))

	def println(self, *args):
		self.print(*args)
		self.print('\n')

	def println_array(self, arr, sep=' '):
		self.println(sep.join((str(x) for x in arr)))

	def flush_output(self):
		self.out_stream.flush()
pythonIO = IO(sys.stdin, sys.stdout)
solve(pythonIO)
pythonIO.flush_output()


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

def solve(s, counts):
	openCount = 0
	closeCount = 0
	posCount = 0
	if n % 2 == 1:
		return posCount
	for i in range(n):
		if s[i] == '(':
			openCount += 1
		else:
			closeCount += 1
		if closeCount - openCount > 2:
			return posCount
		else:
			counts.append([openCount, closeCount])
	if abs(openCount - closeCount) == 2:
		if openCount > closeCount:
			s = s[::-1]
			s = ['(' if c == ')' else ')' for c in s]
			counts = []
			openCount = 0
			closeCount = 0
			for i in range(n):
				if s[i] == '(':
					openCount += 1
				else:
					closeCount += 1
				if closeCount - openCount > 2:
					return posCount
				else:
					counts.append([openCount, closeCount])
		for i in range(n):
			if counts[i][1] - counts[i][0] < 2 and s[i] == ')':
				posCount += 1
			if counts[i][1] > counts[i][0]:
				break
		return posCount
	else:
		return posCount
print(solve(S, []))


def main():
	n = int(input())
	s = input()
	if n == 1:
		print(0)
		return
	dpleft = []
	dpright = []
	for i in range(n):
		dpleft.append([0, 0])
		dpright.append([0, 0])
	left = 0
	right = 0
	for i in range(n):
		if s[i] == '(':
			left += 1
		elif left > 0:
			left -= 1
		else:
			right += 1
		dpleft[i][0] = left
		dpleft[i][1] = right
	left = 0
	right = 0
	for i in range(n - 1, -1, -1):
		if s[i] == ')':
			right += 1
		elif right > 0:
			right -= 1
		else:
			left += 1
		dpright[i][0] = left
		dpright[i][1] = right
	ans = 0
	for i in range(n):
		if i == 0:
			if dpright[i + 1][0] == 0:
				left = 0
				right = dpright[i + 1][1]
				if s[i] == ')':
					left += 1
				else:
					right += 1
				if left == right:
					ans += 1
		elif i == n - 1:
			if dpleft[i - 1][1] == 0:
				left = dpleft[i - 1][0]
				right = 0
				if s[i] == ')':
					left += 1
				else:
					right += 1
				if left == right:
					ans += 1
		elif dpleft[i - 1][1] == 0 and dpright[i + 1][0] == 0:
			left = dpleft[i - 1][0]
			right = dpright[i + 1][1]
			if s[i] == ')':
				left += 1
			else:
				right += 1
			if left == right:
				ans += 1
	print(ans)
main()


n = int(input())
s = input()
p = 0
good = [0] * (n + 1)
options = [0] * n
for i in range(n):
	if s[i] == '(':
		p += 1
		options[i] = p
		good[i + 1] = good[i] + 1
	else:
		p -= 1
		options[i] = p
		good[i + 1] = good[i]
options2 = list(reversed(options))
if abs(p) != 2:
	print(0)
else:
	small = min(options)
	if p == 2:
		if small >= 2:
			print(good[n])
		elif small < 0:
			print(0)
		else:
			index = -1
			while options[index] >= 2:
				index -= 1
			print(good[n] - good[index])
	elif p == -2:
		if small < -2:
			print(0)
		elif small == -2:
			x = options.index(-1)
			print(x + 1 - good[x + 1])


import sys

def main():
	_ = sys.stdin.readline()
	s = sys.stdin.readline().strip()
	prefix = [0] * (len(s) + 1)
	canPrefix = [True] * (len(s) + 1)
	count = 0
	for (i, c) in enumerate(s):
		count = count + 1 if c == '(' else count - 1
		isPossible = True if count >= 0 and canPrefix[i] else False
		prefix[i + 1] = count
		canPrefix[i + 1] = isPossible
	sufix = [0] * (len(s) + 1)
	canSuffix = [True] * (len(s) + 1)
	count = 0
	for (i, c) in enumerate(reversed(s)):
		count = count + 1 if c == ')' else count - 1
		isPossible = True if count >= 0 and canSuffix[len(s) - i] else False
		sufix[len(s) - 1 - i] = count
		canSuffix[len(s) - 1 - i] = isPossible
	ans = 0
	for (i, c) in enumerate(s):
		if canPrefix[i] == False or canSuffix[i + 1] == False:
			continue
		elif c == '(' and prefix[i] - 1 - sufix[i + 1] == 0:
			ans += 1
		elif c == ')' and prefix[i] + 1 - sufix[i + 1] == 0:
			ans += 1
	print(ans)
main()


n = input()
s = input()
r = []
r.append(1 if s[0] == '(' else -1)
for p in s[1:]:
	r.append(r[-1] + (1 if p == '(' else -1))
m = min(r)
if m < -2 or (r[-1] != 2 and r[-1] != -2) or (r[-1] == 2 and m < 0):
	print(0)
else:
	res = 0
	if r[-1] == 2:
		for i in range(len(r) - 1, -1, -1):
			if r[i] == 1:
				break
			if s[i] == '(':
				res += 1
	else:
		for i in range(len(r)):
			if r[i] == -1:
				break
			if s[i] == ')':
				res += 1
		res += 1
	print(res)


n = int(input())
s = input()
a = []
for i in s:
	if i == '(':
		a.append(-1)
	else:
		a.append(1)
b = [0] * n
b[0] = a[0]
for i in range(1, n):
	b[i] = a[i] + b[i - 1]
e = []
c = d = 0
for i in range(n - 1, -1, -1):
	if b[i] >= -1:
		c += 1
	if b[i] >= 3:
		d += 1
	e.append((c, d))
e = e[::-1]
g = 0
ans = 0
for i in range(n):
	if a[i] == -1:
		if e[i][0] == 0 and b[-1] + 2 == 0 and (g == 0):
			ans += 1
	elif e[i][1] == 0 and b[-1] - 2 == 0 and (g == 0):
		ans += 1
	if b[i] > 0:
		g += 1
print(ans)


n = int(input())
skobs = input()
cnt9 = 0
fl = 0
cnt0 = 0
(cnt10, cnt19) = (0, 0)
bz = float('inf')
bz2 = float('-inf')
for y in range(n):
	if skobs[y] == '(':
		cnt9 += 1
	else:
		cnt0 += 1
	if cnt0 - cnt9 > 2:
		fl = 1
	if cnt0 - cnt9 == 1:
		bz = min(bz, y)
for y2 in range(n - 1, -1, -1):
	if skobs[y2] == '(':
		cnt19 += 1
	else:
		cnt10 += 1
	if cnt19 - cnt10 > 2:
		fl = 1
	if cnt19 - cnt10 == 1:
		bz2 = max(bz2, y2)
if abs(cnt9 - cnt0) != 2 or fl or (bz2 != float('-inf') and bz != float('inf')):
	print(0)
elif bz == float('inf') and bz2 != float('-inf'):
	ww = skobs[bz2:]
	print(ww.count('('))
elif bz2 == float('-inf') and bz != float('inf'):
	ww = skobs[:bz + 1]
	print(ww.count(')'))


from typing import *

def main():
	n = int(input())
	s = input().strip()
	ans = solve(n, s)
	print(ans)

def solve(n: int, s: str) -> int:
	if n % 2 == 1:
		return 0
	if s[0] == ')' and s[-1] == '(':
		return 0
	num_closing = s.count(')')
	num_opening = s.count('(')
	if abs(num_closing - num_opening) != 2:
		return 0
	if num_closing < num_opening:
		return solve_switch_opening(n, s)
	else:
		return solve_switch_closing(n, s)

def transform(s: str) -> List[int]:
	(acc, transformed) = (0, [])
	for c in s:
		acc += 1 if c == '(' else -1
		transformed.append(acc)
	return transformed

def solve_switch_opening(n: int, s: str) -> int:
	s_trans = transform(s)
	if len([x for x in s_trans if x < 0]) > 0:
		return 0
	switchable_min_idx = n
	for i in range(n - 1, -1, -1):
		si = s_trans[i]
		if si < 2:
			break
		switchable_min_idx = i
	num_switchables = 0
	for i in range(switchable_min_idx, n):
		if s[i] == '(':
			num_switchables += 1
	return num_switchables

def solve_switch_closing(n: int, s: str) -> int:
	s_trans = transform(s)
	if len([x for x in s_trans if x < -2]) > 0:
		return 0
	switchable_max_idx = -1
	for i in range(n):
		si = s_trans[i]
		switchable_max_idx = i
		if si < 0:
			break
	num_switchables = 0
	for i in range(0, switchable_max_idx + 1):
		if s[i] == ')':
			num_switchables += 1
	return num_switchables
main()


import sys
n = int(input())
S = input()
L = [0]
for s in S:
	if s == '(':
		L.append(L[-1] + 1)
	else:
		L.append(L[-1] - 1)
if L[-1] == 2:
	if min(L) < 0:
		print(0)
		sys.exit()
	ANS = 0
	for j in range(n, -1, -1):
		if L[j] < 2:
			break
	for k in range(j, n):
		if S[k] == '(':
			ANS += 1
	print(ANS)
elif L[-1] == -2:
	if min(L) < -2:
		print(0)
		sys.exit()
	ANS = 0
	for j in range(1, n + 1):
		if L[j] < 0:
			break
	for k in range(j - 1, -1, -1):
		if S[k] == ')':
			ANS += 1
	print(ANS)
else:
	print(0)


n = int(input())
s = input()
pre = []
suf = []
for (i, x) in enumerate(s):
	if len(pre) == 0:
		pre.append([1, 0] if x == '(' else [0, 1])
	else:
		(pre1, pre2) = pre[-1]
		(cur1, cur2) = (None, None)
		if x == '(':
			(cur1, cur2) = (pre1 + 1, pre2)
		elif pre1 > 0:
			(cur1, cur2) = (pre1 - 1, pre2)
		else:
			(cur1, cur2) = (pre1, pre2 + 1)
		pre.append([cur1, cur2])
for (i, x) in enumerate(s[::-1]):
	if len(suf) == 0:
		suf.append([0, 1] if x == ')' else [1, 0])
	else:
		(pre1, pre2) = suf[-1]
		(cur1, cur2) = (None, None)
		if x == ')':
			(cur1, cur2) = (pre1, pre2 + 1)
		elif pre2 > 0:
			(cur1, cur2) = (pre1, pre2 - 1)
		else:
			(cur1, cur2) = (pre1 + 1, pre2)
		suf.append([cur1, cur2])
suf = suf[::-1]
ans = 0
for (i, x) in enumerate(s):
	(pre1, pre2, suf1, suf2) = (0, 0, 0, 0)
	if i > 0:
		(pre1, pre2) = pre[i - 1]
	if i + 1 < n:
		(suf1, suf2) = suf[i + 1]
	if x == ')':
		pre1 += 1
	elif pre1 > 0:
		pre1 -= 1
	else:
		pre2 += 1
	if pre2 == 0 and suf1 == 0 and (pre1 == suf2):
		ans += 1
print(ans)


import sys
from collections import deque
import math
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
li = lambda : list(input_())
pr = lambda x: print(x)
f = lambda : sys.stdout.flush()
n = ii()
s = li()
a = []
for i in range(n):
	if s[i] == ')' and len(a) > 0 and (a[-1][0] == '('):
		a.pop()
	else:
		a.append([s[i], i + 1])
if n % 2 or len(a) == 0:
	print(0)
elif len(a) == 2 and a[0][0] == a[1][0]:
	if a[0][0] == '(':
		print((n - a[1][1]) // 2 + 1)
	else:
		print(a[0][1] // 2 + 1)
else:
	print(0)


size = int(input())
seq = input()
offsets = []
if seq[0] == '(':
	offsets.append(1)
else:
	offsets.append(-1)
for char in seq[1:]:
	if char == '(':
		offsets.append(offsets[-1] + 1)
	else:
		offsets.append(offsets[-1] - 1)
min_offsets = [offsets[-1]] * size
for idx in range(size - 2, -1, -1):
	min_offsets[idx] = min(min_offsets[idx + 1], offsets[idx])
counter = 0
for (idx, char) in enumerate(seq):
	if idx > 0:
		if offsets[idx - 1] < 0:
			break
	proposed_offset = -2
	if char == ')':
		proposed_offset = 2
	if min_offsets[idx] + proposed_offset >= 0 and offsets[-1] + proposed_offset == 0:
		counter += 1
print(counter)


import sys, math
from collections import defaultdict
n = int(input())
st = input()
if n % 2:
	print(0)
	exit()
x = st.count('(')
if x not in (n // 2 - 1, n // 2 + 1):
	print(0)
	exit()
rem = ')'
if x > n // 2:
	rem = '('
arrpr = [0] * (n + 2)
arrpo = [0] * (n + 2)
for i in range(n):
	if st[i] == '(':
		arrpr[i + 1] += arrpr[i] + 1
	else:
		arrpr[i + 1] = arrpr[i] - 1
	if st[n - 1 - i] == ')':
		arrpo[n - i] = arrpo[n + 1 - i] + 1
	else:
		arrpo[n - i] = arrpo[n + 1 - i] - 1
valpr = [False] * (n + 2)
valpo = [False] * (n + 2)
valpr[0] = valpo[-1] = True
for i in range(1, n + 1):
	valpr[i] = arrpr[i - 1] >= 0 and valpr[i - 1]
	valpo[n + 1 - i] = arrpo[n + 1 - i] >= 0 and valpo[n - i + 2]
res = 0
for i in range(1, n + 1):
	if valpr[i - 1] == False or valpo[i + 1] == False:
		continue
	if arrpr[i - 1] - arrpo[i + 1] == 1 and st[i - 1] == '(' and (arrpr[i - 1] > 0):
		res += 1
	elif st[i - 1] == ')' and arrpr[i - 1] - arrpo[i + 1] == -1 and (arrpo[i + 1] > 0):
		res += 1
print(res)


def c(a):
	if a == '(':
		return 1
	else:
		return -1
n = int(input())
s = input()
sc = s
rev = []
for i in sc:
	rev.append(i)
rev = rev[::-1]
for i in range(n):
	if rev[i] == ')':
		rev[i] = '('
	else:
		rev[i] = ')'
pre = [0] * (n + 1)
suf = [0] * (n + 1)
okpre = [False] * (n + 1)
oksuf = [False] * (n + 1)
okpre[0] = True
oksuf[n] = True
for i in range(n):
	pre[i + 1] = pre[i] + c(s[i])
	okpre[i + 1] = okpre[i] & (pre[i + 1] >= 0)
	suf[n - i - 1] = suf[n - i] + c(rev[i])
	oksuf[n - i - 1] = oksuf[n - i] & (suf[n - i - 1] >= 0)
ans = 0
for i in range(n):
	if not oksuf[i + 1] or not okpre[i]:
		continue
	if s[i] == '(':
		if pre[i] > 0 and pre[i] - suf[i + 1] - 1 == 0:
			ans += 1
	elif pre[i] + 1 - suf[i + 1] == 0:
		ans += 1
print(ans)


from collections import deque
import pdb
import heapq
from heapq import *
from pprint import pprint
from bisect import *
mod = 99999999999

def rI():
	return [int(i) for i in input().split()]
n = rI()[0]
s = input()
if n % 2 == 1:
	print(0)
	exit()
leftstack = [0 for i in range(n)] + [0]
rightstack = [0 for i in range(n)] + [0]
st = []
for i in range(n):
	if s[i] == '(':
		leftstack[i] = leftstack[i - 1] + 1
	else:
		leftstack[i] = leftstack[i - 1] - 1
	if leftstack[i] < 0:
		leftstack[i] = mod
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		rightstack[i] = rightstack[i + 1] + 1
	else:
		rightstack[i] = rightstack[i + 1] - 1
	if rightstack[i] < 0:
		rightstack[i] = mod * 2
st = 0
e = n
if s[0] == '(':
	st = 1
if s[n - 1] == ')':
	e = n - 1
out = 0
for i in range(st, e):
	if s[i] == ')':
		if leftstack[i - 1] + 1 == rightstack[i + 1]:
			out += 1
	elif leftstack[i - 1] == rightstack[i + 1] + 1:
		out += 1
print(out)


n = int(input())
s = str(input())
arr1 = []
arr11 = []
count = 0
flag = 0
for i in range(len(s)):
	if s[i] == '(':
		count += 1
	else:
		count -= 1
	if count < 0:
		flag = 1
	if flag == 0:
		arr11.append(1)
	else:
		arr11.append(-1)
	arr1.append(count)
arr2 = [0] * n
arr22 = [0] * n
count2 = 0
flag = 0
for i in range(len(s) - 1, -1, -1):
	if s[i] == '(':
		count2 += 1
	else:
		count2 -= 1
	if count2 > 0:
		flag = 1
	if flag == 0:
		arr22[i] = 1
	else:
		arr22[i] = -1
	arr2[i] = count2
ans = 0
for i in range(n):
	if i == 0:
		if s[i] == ')' and i < n - 1 and (arr2[i + 1] == -1) and (arr22[i + 1] == 1):
			ans += 1
	elif i == n - 1:
		if s[i] == '(' and i > 0 and (arr1[i - 1] == 1) and (arr11[i - 1] == 1):
			ans += 1
	elif s[i] == '(':
		if arr1[i - 1] + arr2[i + 1] == 1 and arr11[i - 1] == 1 and (arr22[i + 1] == 1):
			ans += 1
	elif arr1[i - 1] + arr2[i + 1] == -1 and arr11[i - 1] == 1 and (arr22[i + 1] == 1):
		ans += 1
print(ans)


def isregular(s):
	ls = 0
	rs = 0
	for char in s:
		if char == '(':
			ls += 1
		else:
			rs += 1
		if rs > ls:
			return False
	if ls == rs:
		return True
	return False
n = int(input())
s = input()
if n % 2 == 1:
	print(0)
else:
	a = s.count('(')
	b = n - a
	diff = [0]
	for i in range(n):
		if s[i] == '(':
			diff.append(diff[-1] + 1)
		else:
			diff.append(diff[-1] - 1)
	if a == b + 2:
		if -1 in diff:
			print(0)
		else:
			backdiff = diff[::-1]
			last = backdiff.index(1)
			print(s[-last:].count('('))
	elif b == a + 2:
		if -3 in diff:
			print(0)
		else:
			first = diff.index(-1)
			print(s[:first].count(')'))
	else:
		print(0)