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



if __name__ == '__main__':
	main()