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>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
long long sqr(long long x) { return x * x; }
long double sqrd(long double x) { return x * x; }
inline long long gcd(long long a, long long b) {
  while (b) {
    a %= b, swap(a, b);
  }
  return a;
}
inline long long lcm(long long a, long long b) {
  return a * b / max(1ll, gcd(a, b));
}
mt19937 Random((long long)time(0));
inline long long rnd(long long x) { return Random() % x; }
const long long INF = (long long)1e9 + 282;
const long long MOD = (long long)1e9 + 7;
const long double PI = acosl(-1.0);
const long long N = 1e6 + 10;
long long pref[N], suf[N];
bool cp[N], cs[N];
void $main() {
  long long n;
  cin >> n;
  string second;
  cin >> second;
  second = "#" + second;
  cp[0] = 1;
  for (long long i = 1; i <= n; i++) {
    pref[i] = pref[i - 1];
    pref[i] += second[i] == '(';
    pref[i] -= second[i] == ')';
    cp[i] = cp[i - 1];
    cp[i] &= pref[i] >= 0;
  }
  cs[n + 1] = 1;
  for (long long i = n; i > 0; i--) {
    suf[i] = suf[i + 1];
    suf[i] += second[i] == '(';
    suf[i] -= second[i] == ')';
    cs[i] = cs[i + 1];
    cs[i] &= suf[i] <= 0;
  }
  long long ans = 0;
  for (long long i = 1; i <= n; i++) {
    if (second[i] == '(') {
      if (cp[i - 1] && cs[i + 1] && pref[i - 1] + suf[i + 1] - 1 == 0) {
        ans++;
      }
    } else {
      if (cp[i - 1] && cs[i + 1] && pref[i - 1] + suf[i + 1] + 1 == 0) {
        ans++;
      }
    };
  }
  cout << ans;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios_base::fixed, ios_base::floatfield);
  cout.precision(12);
  $main();
}
