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
import sys, os
# import numpy as np
from math import sqrt, gcd, ceil, log, floor 
from math import factorial as fact
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))
# read_f = lambda file:  list(map(int, file.readline().strip().split()))
# from time import time
# sys.setrecursionlimit(5*10**6)

MOD = 10**9 + 7


def main():
	# file1 = open("C:\\Users\\shank\\Desktop\\Comp_Code\\input.txt", "r")
	# n = int(file1.readline().strip()); 
	# arr = list(map(int, file1.read().strip().split(" ")))
	# file1.close()
	# n = int(input()
	# ans_ = []
	# for _ in range(int(input())):
	
	n  =int(input()); s = input().strip()
	if n%2:print(0); exit()

	pref = [0]*n; suf = [0]*n; 
	invalidpref = [0]*n; invalidsuf = [0]*n

	pref[0] = [1, -1][s[0] == ")"]
	suf[-1] = [1, -1][s[-1] == "("]
	invalidpref[0] = (s[0] == ")")
	invalidsuf[-1] = (s[-1] == "(")

	for i in range(1,n):
		pref[i] = pref[i-1]+[1, -1][s[i] == ")"]
		suf[n-i-1] = suf[n-i]+[1, -1][s[n-i-1] == "("]

		invalidpref[i] = invalidpref[i-1] | (pref[i] < 0) 
		invalidsuf[n-i-1] = invalidsuf[n-i] | (suf[n-i-1] < 0)

	# print(pref, suf)
	# print(invalidpref, invalidsuf)

	ans = 0
	if s[0] == ")" and not invalidsuf[0]:ans += (1-suf[1])==0
	if s[-1] == "(" and not invalidpref[-1]:ans += (pref[-2]-1)==0

	# print(ans, "*"*10)

	for i in range(1,n-1):
		if invalidpref[i-1] or invalidsuf[i+1]:continue
		elif s[i] == ")" and (pref[i-1]+1-suf[i+1])==0:
			ans += 1; 
			# print(i, ans)
		elif s[i] == "(" and  (pref[i-1]-1-suf[i+1])==0:
			ans += 1; 
			# print(i, ans)
		# print(i, ans)
	print(ans)





	# for i in ans_:
	# 	print(i)

		# print(f1())
	# print(("\n").join(ans))




	# file = open("output.txt", "w")
	# file.write(ans+"\n")
	# file.close()

if __name__ == "__main__":
	main()



"""

(()((())()
(())(())()  4
(()()())()  5
(()(()))()  6
(()((())))  9


"""