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: introductory

Starter code:

Solutions:
def ii():
    return int(input())
def mi():
    return list(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
    else:
        if a[n - 1] == -2 and mm == -2 and m[j - 1] >= 0:
            ans += 1

print(ans)


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): # cas de fin
		dead = True
		break
	if ( cpt < 0): #on doit utiliser un joker avant
		if(plusEnd or cptPlus==0):#on en a pas ou déjà utilisé
			dead = True
			break
		else:
			plusEnd = True
			#on considère qu'on l'a fait
			cpt +=2

	if cpt<2:
		cptMoins =0
if(dead):
	print(0)
else:
	if( plusEnd and cpt ==0):
		print(cptPlus)
	elif ( not plusEnd and cpt ==2):
		print(cptMoins)
	else:
		print(0)


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





_ = 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:
    # x <= ia
    ia = 0
    while ia < len(sums) and sums[ia] >= 0:
        ia += 1

    # x > ib
    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:
    # x <= ia
    ia = 0
    while ia < len(sums) and sums[ia] >= 0:
        ia += 1

    # x > ib
    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)


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(idx)
# print(offsets)
# print(min_offsets)
print(counter)


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

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)
        return
    ANS=0

    for j in range(n,-1,-1):
        if L[j]<2:
            #print(j)
            break

    for k in range(j,n):
        if S[k]=="(":
            ANS+=1

    print(ANS)

elif L[-1]==-2:
    if min(L)<-2:
        print(0)
        return
    ANS=0

    for j in range(1,n+1):
        if L[j]<0:
            #print(j)
            break

    for k in range(j-1,-1,-1):
        if S[k]==")":
            ANS+=1

    print(ANS)

else:
    print(0)


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)

#from random import random, randint
from sys import stdout, stdin
import math

#n, k = map(int, input().split())
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())
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])
#s1[0][0]=8
#print(s1,s2)
if s[0]=='(':
	s1[0][0]+=1
else:
	s1[0][1]+=1
#print(s1)
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
	#print(s1)
if s[-1]=='(':
	s2[-1][0]+=1
else:
	s2[-1][1]+=1
#print(s2)
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
#print(s2)
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
		#print("CHECK")
		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(i,ans)
print(ans)


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))
else:
    if curs != -2:
        print(0)
    else:
        print(int(wasm/2) + 1)

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))
else:
    if curs != -2:
        print(0)
    else:
        print(int(wasm/2) + 1)

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())
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=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().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 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
	# print(a) # debug
	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()

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)

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 = 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 n % 2 == 1 or len(stk) == 0:
  print(0)
elif 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)

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,[]))

n=int(input())
s=input()
a=[]
for i in s:
    if i=='(':
        a.append(-1)
    else:
        a.append(1)
#print (a)
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
    else:
        if e[i][1]==0 and (b[-1]-2)==0 and g==0:
            ans+=1
    if b[i]>0:
        g+=1
#print (b)
#print(e)
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)

# Created by nikita at 30/12/2018

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]

# print(prefBal)
# print(prefCan)
# print(suffBal)
# print(suffCan)

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)