#include <bits/stdc++.h>
using namespace std;
long long modexpo(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % 1000000007;
    a = (a * a) % 1000000007;
    b >>= 1;
  }
  return res;
}
long long expo(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a);
    a = (a * a);
    b >>= 1;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i += 6) {
    if ((n % i == 0) || (n % (i + 2) == 0)) return false;
  }
  return true;
}
long double dist(long long x1, long long y1, long long x2, long long y2) {
  return (long double)sqrt(
      (long double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
long long squaredist(long long x1, long long y1, long long x2, long long y2) {
  return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
long long nCr(long long n, long long r) {
  if (r == 0) return 1;
  return (n * nCr(n - 1, r - 1)) / r;
}
signed main() {
  long long n;
  cin >> n;
  string str;
  cin >> str;
  stack<pair<char, long long> > st;
  for (long long i = 0; i < n; i++) {
    if (st.empty()) {
      st.push(make_pair(str[i], i + 1));
    } else {
      if (st.top().first == '(' && str[i] == ')')
        st.pop();
      else
        st.push(make_pair(str[i], i + 1));
    }
  }
  if (st.size() % 2 == 1 || st.size() > 2)
    cout << 0 << endl;
  else if (st.size() == 0) {
    cout << 0 << endl;
  } else {
    string ans = "";
    long long i, j;
    ans += st.top().first;
    i = st.top().second;
    st.pop();
    ans += st.top().first;
    j = st.top().second;
    st.pop();
    if (ans[0] != ans[1]) {
      cout << 0 << endl;
      return 0;
    }
    if (ans[0] == '(') {
      long long ans = 0;
      i--;
      for (long long k = i; k < n; k++)
        if (str[k] == '(') ans++;
      cout << ans << endl;
    } else {
      long long ans = 0;
      for (long long k = 0; k < j; k++)
        if (str[k] == ')') ans++;
      cout << ans << endl;
    }
  }
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long modexpo(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % 1000000007;
    a = (a * a) % 1000000007;
    b >>= 1;
  }
  return res;
}
long long expo(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a);
    a = (a * a);
    b >>= 1;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i += 6) {
    if ((n % i == 0) || (n % (i + 2) == 0)) return false;
  }
  return true;
}
long double dist(long long x1, long long y1, long long x2, long long y2) {
  return (long double)sqrt(
      (long double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
long long squaredist(long long x1, long long y1, long long x2, long long y2) {
  return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
long long nCr(long long n, long long r) {
  if (r == 0) return 1;
  return (n * nCr(n - 1, r - 1)) / r;
}
signed main() {
  long long n;
  cin >> n;
  string str;
  cin >> str;
  stack<pair<char, long long> > st;
  for (long long i = 0; i < n; i++) {
    if (st.empty()) {
      st.push(make_pair(str[i], i + 1));
    } else {
      if (st.top().first == '(' && str[i] == ')')
        st.pop();
      else
        st.push(make_pair(str[i], i + 1));
    }
  }
  if (st.size() % 2 == 1 || st.size() > 2)
    cout << 0 << endl;
  else if (st.size() == 0) {
    cout << 0 << endl;
  } else {
    string ans = "";
    long long i, j;
    ans += st.top().first;
    i = st.top().second;
    st.pop();
    ans += st.top().first;
    j = st.top().second;
    st.pop();
    if (ans[0] != ans[1]) {
      cout << 0 << endl;
      return 0;
    }
    if (ans[0] == '(') {
      long long ans = 0;
      i--;
      for (long long k = i; k < n; k++)
        if (str[k] == '(') ans++;
      cout << ans << endl;
    } else {
      long long ans = 0;
      for (long long k = 0; k < j; k++)
        if (str[k] == ')') ans++;
      cout << ans << endl;
    }
  }
  return 0;
}

```