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
input = sys.stdin.readline

n = int(input())
s = list(input().rstrip())
c1, c2 = 0, 0
for i in s:
    if i == "(":
        c1 += 1
    else:
        c2 += 1
if abs(c1 - c2) ^ 2:
    ans = 0
else:
    x, now = [0] * n, 0
    ans, m = 0, n
    if c1 > c2:
        for i in range(n):
            now += 1 if s[i] == "(" else -1
            x[i] = now
        for i in range(n - 1, -1, -1):
            if s[i] == ")":
                m = min(m, x[i])
            elif 1 < m and 1 < x[i]:
                ans += 1
    else:
        for i in range(n - 1, -1, -1):
            now += 1 if s[i] == ")" else -1
            x[i] = now
        for i in range(n):
            if s[i] == "(":
                m = min(m, x[i])
            elif 1 < m and 1 < x[i]:
                ans += 1
    if min(x) < 0:
        ans = 0
print(ans)