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
#include <bits/stdc++.h>
using namespace std;
const int MM = 1e6 + 5;
const int inf = 1e9;
struct Node {
  Node *l = 0, *r = 0;
  int lo, hi, mset = inf, madd = 0, val = inf;
  Node(int lo, int hi) : lo(lo), hi(hi) {}
  int query(int L, int R) {
    if (R <= lo || hi <= L) return inf;
    if (L <= lo && hi <= R) return val;
    push();
    return min(l->query(L, R), r->query(L, R));
  }
  void set(int L, int R, int x) {
    if (R <= lo || hi <= L) return;
    if (L <= lo && hi <= R)
      mset = val = x, madd = 0;
    else {
      push(), l->set(L, R, x), r->set(L, R, x);
      val = min(l->val, r->val);
    }
  }
  void add(int L, int R, int x) {
    if (R <= lo || hi <= L) return;
    if (L <= lo && hi <= R) {
      if (mset != inf)
        mset += x;
      else
        madd += x;
      val += x;
    } else {
      push(), l->add(L, R, x), r->add(L, R, x);
      val = min(l->val, r->val);
    }
  }
  void push() {
    if (!l) {
      int mid = lo + (hi - lo) / 2;
      l = new Node(lo, mid);
      r = new Node(mid, hi);
    }
    if (mset != inf)
      l->set(lo, hi, mset), r->set(lo, hi, mset), mset = inf;
    else if (madd)
      l->add(lo, hi, madd), r->add(lo, hi, madd), madd = 0;
  }
};
int n, suff[MM];
string s;
Node* st;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> s;
  s = ' ' + s;
  int dep = 0;
  st = new Node(0, n + 1);
  for (int i = 1; i <= n; i++) {
    dep += (s[i] == '(' ? 1 : -1);
    st->set(i, i + 1, dep);
  }
  for (int i = n; i >= 1; i--) {
    suff[i] = suff[i + 1] + (s[i] == '(' ? 1 : -1);
  }
  int pref = 0, ans = 0;
  for (int i = 1; i <= n; i++) {
    st->add(i, n + 1, (s[i] == '(' ? -1 : 1));
    st->add(i, n + 1, (s[i] == '(' ? -1 : 1));
    if (pref + (s[i] == '(' ? -1 : 1) + suff[i + 1] == 0 &&
        st->query(1, n + 1) >= 0)
      ans++;
    st->add(i, n + 1, (s[i] == '(' ? 1 : -1));
    st->add(i, n + 1, (s[i] == '(' ? 1 : -1));
    pref += (s[i] == '(' ? 1 : -1);
  }
  cout << ans << "\n";
}
