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

n=int(input())
S=input()

L=[0]
for s in S:
    if s=="(":
        L.append(L[-1]+1)
    else:
        L.append(L[-1]-1)

if L[-1]==2:
    if min(L)<0:
        print(0)
        sys.exit()
    ANS=0

    for j in range(n,-1,-1):
        if L[j]<2:
            #print(j)
            break

    for k in range(j,n):
        if S[k]=="(":
            ANS+=1

    print(ANS)

elif L[-1]==-2:
    if min(L)<-2:
        print(0)
        sys.exit()
    ANS=0

    for j in range(1,n+1):
        if L[j]<0:
            #print(j)
            break

    for k in range(j-1,-1,-1):
        if S[k]==")":
            ANS+=1

    print(ANS)

else:
    print(0)
