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 = input()
s = raw_input().strip()

pre = [0 for i in xrange(n + 1)]

bctr = n
actr = pctr = 0
acnt = pcnt = 0

for i in xrange(1, n + 1):
    x = -1 if s[i - 1] == ')' else 1
    pre[i] = pre[i - 1] + x
    if pre[i] < 0 and bctr == n: bctr = i - 1

if abs(pre[-1]) != 2:
    print 0
    exit()

for i in xrange(n, 0, -1):
    if pre[i] < -2 and acnt == 0:
        actr = i - 1
        acnt = 1
    if pre[i] < 2 and pcnt == 0:
        pctr = i - 1
        pcnt = 1

    if pcnt != 0 and acnt != 0: break

ans = 0
for i in xrange(n):
    if s[i] == ')' and i != n - 1:
        if pre[-1] == -2 and bctr >= i and actr <= i: ans += 1
    if s[i] == '(' and i != 0:
        if pre[-1] == 2 and bctr >= i and pctr <= i and pre[i + 1] >= 2: ans += 1

print ans