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())
str = input()
balance = 0
for x in str:
  if x == '(':
    balance += 1
  else:
    balance -= 1

pre = []
pre_balance = 0
for x in str:
  if x == '(':
    pre_balance += 1
  else:
    pre_balance -= 1
  pre.append(pre_balance)

suf = []
lowest = []
suf_balance = 0
high = 0
low = 0
for x in reversed(str):
  suf.append(suf_balance)
  high = max(high, suf_balance)
  low = suf_balance - high
  lowest.append(low)
  if x == '(':
    suf_balance += 1
  else:
    suf_balance -= 1
  
suf.reverse()
lowest.reverse()
ans = 0

if balance == 2:
  is_bad = False
  for i, x in enumerate(str):
    if is_bad:
      break
    if x == '(':
      new_pre = pre[i] - 2
      if new_pre >= 0 and new_pre == -suf[i] and new_pre >= -lowest[i]:
        if i + 1 == n or str[-1] != '(':
          ans += 1
    if pre[i] < 0:
      is_bad = True
elif balance == -2:
  is_bad = False
  for i, x in enumerate(str):
    if is_bad:
      break
    if x == ')':
      new_pre = pre[i] + 2
      if new_pre >= 0 and new_pre == -suf[i] and new_pre >= -lowest[i]:
        if i + 1 == n or str[-1] != '(':
          ans += 1
    if pre[i] < 0:
      is_bad = True
print(ans)