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