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,math
from collections import defaultdict
n = int(input())
#n,k = [int(__) for __ in input().split()]
#arr = [int(__) for __ in input().split()]
st = input()
#lines = sys.stdin.readlines()

if n%2:
    print(0)
    exit()
x = st.count('(')
if x not in (n // 2 - 1, n // 2 + 1):
    print(0)
    exit()
rem = ')'
if x > n // 2:
    rem = '('
arrpr = [0] * (n+2)
arrpo = [0] * (n+2)
for i in range(n):
    if st[i] == '(':
        arrpr[i+1] += arrpr[i] + 1
    else:
        arrpr[i+1] = arrpr[i] - 1
    if st[n-1-i] == ')':
        arrpo[n-i] = arrpo[n+1-i] + 1
    else:
        arrpo[n-i] = arrpo[n+1-i] - 1
#print(arrpr)
#print(arrpo)
valpr = [False] * (n+2)
valpo = [False] * (n+2)
valpr[0] = valpo[-1] = True
for i in range(1,n+1):
    valpr[i] = arrpr[i-1] >= 0 and valpr[i-1]
    valpo[n+1-i] = arrpo[n+1-i] >= 0 and valpo[n-i+2]
res = 0
for i in range(1,n+1):
    if valpr[i-1] == False or valpo[i+1] == False:
        continue
    if arrpr[i-1] - arrpo[i+1] == 1 and st[i-1] == '(' and arrpr[i-1] > 0:
        #print(i)
        res += 1
    elif st[i-1] == ')' and arrpr[i-1] - arrpo[i+1] == -1 and arrpo[i+1] > 0:
        res += 1
#print(valpr)
#print(valpo)
print(res)