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 ≤ n ≤ 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
a=int(raw_input())

s=raw_input()

esquerda=0

direita=0


l=[]

l1=[]

ans=True

for i in s:
	if i=='(':
		esquerda+=1
	else:
		esquerda-=1
	if esquerda<0:
		ans=False
	if ans:
		l.append(esquerda)
	else:
		l.append(-1)
ans=True
for i in s[::-1]:
	if i==')':
		direita+=1
	else:
		direita-=1
	if direita<0:
		ans=False
	if ans:
		l1.append(direita)
	else:
		l1.append(-1)

cont=0
l1=l1[::-1]

l.insert(0,0)
l1.insert(0,0)
l.append(0)
l1.append(0)
c=0
for i in xrange(1,a+1):
	if s[c]=='(':
		if l[i-1]-l1[i+1]==1 and l[i-1]>=0 and l1[i+1]>=0:
			cont+=1
	else:
		if l1[i+1]-l[i-1]==1 and l1[i+1]>=0 and l[i-1]>=0:
			cont+=1
	c+=1
print cont

		
