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
n = int(input())
s = input()

def sol(n, S):
    L = [0]
    for s in S:
        if s == "(":
            L.append(L[-1] + 1)
        else:
            L.append(L[-1] - 1)
    ANS = 0
    L = L[1:]
    if L[-1] == 2:
        if min(L) < 0:
            return 0
        for j in range(n-1, -1, -1):
            if L[j] < 2:
                break
        for k in range(j+1, n, 1):
            if S[k] == '(':
                ANS += 1
    elif L[-1] == -2:
        if min(L) < -2:
            return 0
        for j in range(n):
            if L[j] < 0:
                break
        for k in range(j, -1, -1):
            if S[k] == ')':
                ANS += 1
    else:
        ANS = 0
    return ANS

print(sol(n, s))