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
# bayan
from collections import deque
import pdb
import heapq
from heapq import *
from pprint import pprint
from bisect import *

mod = 99999999999


def rI():
    return [int(i) for i in input().split()]


n = rI()[0]
s = input()

if(n % 2 == 1):
    print(0)
    exit()


leftstack = [0 for i in range(n)] + [0]
rightstack = [0 for i in range(n)] + [0]

st = []
for i in range(n):
    if(s[i] == '('):
        leftstack[i] = leftstack[i - 1] + 1
    else:
        leftstack[i] = leftstack[i - 1] - 1
    if(leftstack[i] < 0):
        leftstack[i] = mod

for i in range(n - 1, -1, -1):
    if(s[i] == ')'):
        rightstack[i] = rightstack[i + 1] + 1
    else:
        rightstack[i] = rightstack[i + 1] - 1
    if(rightstack[i] < 0):
        rightstack[i] = mod * 2

# pdb.set_trace()
st = 0
e = n
if(s[0] == '('):
    st = 1
if(s[n - 1] == ')'):
    e = n - 1
out = 0
for i in range(st, e):
    # print(leftstack[i], rightstack[i])
    if(s[i] == ')'):
        if((leftstack[i - 1] + 1) == (rightstack[i + 1])):
            out += 1
    else:
        if((leftstack[i - 1]) == (rightstack[i + 1] + 1)):
            out += 1


# print(leftstack)
# print(rightstack)
print(out)
