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