#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T = ll>
inline T in() {
  T ret;
  cin >> ret;
  return ret;
}
template <typename T>
class segment_tree {
 private:
  ll size;
  vector<T> data;
  function<T(T, T)> operation;
  T identity;

 public:
  segment_tree(ll sz, function<T(T, T)> opr, T id)
      : operation(opr), identity(id) {
    size = 1;
    while (size < sz) size <<= 2;
    data.resize(size * 2);
    fill((data).begin(), (data).end(), identity);
  }
  void set(ll idx, T v) { data[idx + size - 1] = v; }
  T get(ll idx) { return data[idx + size - 1]; }
  void update() {
    for (ll i = (size - 1) - 1; i >= 0; --i) {
      data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
    }
  }
  void update(ll idx, T v) {
    idx += size - 1;
    data[idx] = v;
    while (idx > 0) {
      idx = (idx - 1) / 2;
      data[idx] = operation(data[idx * 2 + 1], data[idx * 2 + 2]);
    }
  }
  T query(ll l, ll r) {
    l += size - 1;
    r += size - 1;
    T L = identity, R = identity;
    while (l < r) {
      if ((l & 1) == 0) L = operation(L, data[l++]);
      if ((r & 1) == 0) R = operation(data[--r], R);
      l >>= 1;
      r >>= 1;
    }
    return operation(L, R);
  }
  static segment_tree<T> sum(ll sz) {
    return move(segment_tree<T>(
        sz, [](T v1, T v2) { return v1 + v2; }, static_cast<T>(0)));
  }
  static segment_tree<T> max(ll sz) {
    return move(segment_tree<T>(
        sz, [](T v1, T v2) { return v1 > v2 ? v1 : v2; },
        numeric_limits<T>::min()));
  }
  static segment_tree<T> min(ll sz) {
    return move(segment_tree<T>(
        sz, [](T v1, T v2) { return v1 < v2 ? v1 : v2; },
        numeric_limits<T>::max()));
  }
};
signed main() {
  ll n = in();
  string bracket = in<string>();
  vector<ll> imos(n + 1);
  for (ll i = 0, i_len = (n); i < i_len; ++i)
    imos[i] = bracket[i] == '(' ? 1 : -1;
  for (ll i = 0, i_len = (n); i < i_len; ++i) imos[i + 1] += imos[i];
  auto stmin = segment_tree<ll>::min(n);
  for (ll i = 0, i_len = (n); i < i_len; ++i) stmin.set(i, imos[i]);
  stmin.update();
  ll ans = 0;
  if (imos[n - 1] == 2) {
    for (ll i = 0, i_len = (n); i < i_len; ++i)
      if (bracket[i] == '(' && stmin.query(0, i) >= 0 && stmin.query(i, n) >= 2)
        ++ans;
  } else if (imos[n - 1] == -2) {
    for (ll i = 0, i_len = (n); i < i_len; ++i)
      if (bracket[i] == ')' && stmin.query(0, i) >= 0 &&
          stmin.query(i, n) >= -2)
        ++ans;
  }
  cout << ans << endl;
}

### Prompt

Your challenge is to write a cpp solution 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;
using ll = long long;
template <typename T = ll>
inline T in() {
  T ret;
  cin >> ret;
  return ret;
}
template <typename T>
class segment_tree {
 private:
  ll size;
  vector<T> data;
  function<T(T, T)> operation;
  T identity;

 public:
  segment_tree(ll sz, function<T(T, T)> opr, T id)
      : operation(opr), identity(id) {
    size = 1;
    while (size < sz) size <<= 2;
    data.resize(size * 2);
    fill((data).begin(), (data).end(), identity);
  }
  void set(ll idx, T v) { data[idx + size - 1] = v; }
  T get(ll idx) { return data[idx + size - 1]; }
  void update() {
    for (ll i = (size - 1) - 1; i >= 0; --i) {
      data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
    }
  }
  void update(ll idx, T v) {
    idx += size - 1;
    data[idx] = v;
    while (idx > 0) {
      idx = (idx - 1) / 2;
      data[idx] = operation(data[idx * 2 + 1], data[idx * 2 + 2]);
    }
  }
  T query(ll l, ll r) {
    l += size - 1;
    r += size - 1;
    T L = identity, R = identity;
    while (l < r) {
      if ((l & 1) == 0) L = operation(L, data[l++]);
      if ((r & 1) == 0) R = operation(data[--r], R);
      l >>= 1;
      r >>= 1;
    }
    return operation(L, R);
  }
  static segment_tree<T> sum(ll sz) {
    return move(segment_tree<T>(
        sz, [](T v1, T v2) { return v1 + v2; }, static_cast<T>(0)));
  }
  static segment_tree<T> max(ll sz) {
    return move(segment_tree<T>(
        sz, [](T v1, T v2) { return v1 > v2 ? v1 : v2; },
        numeric_limits<T>::min()));
  }
  static segment_tree<T> min(ll sz) {
    return move(segment_tree<T>(
        sz, [](T v1, T v2) { return v1 < v2 ? v1 : v2; },
        numeric_limits<T>::max()));
  }
};
signed main() {
  ll n = in();
  string bracket = in<string>();
  vector<ll> imos(n + 1);
  for (ll i = 0, i_len = (n); i < i_len; ++i)
    imos[i] = bracket[i] == '(' ? 1 : -1;
  for (ll i = 0, i_len = (n); i < i_len; ++i) imos[i + 1] += imos[i];
  auto stmin = segment_tree<ll>::min(n);
  for (ll i = 0, i_len = (n); i < i_len; ++i) stmin.set(i, imos[i]);
  stmin.update();
  ll ans = 0;
  if (imos[n - 1] == 2) {
    for (ll i = 0, i_len = (n); i < i_len; ++i)
      if (bracket[i] == '(' && stmin.query(0, i) >= 0 && stmin.query(i, n) >= 2)
        ++ans;
  } else if (imos[n - 1] == -2) {
    for (ll i = 0, i_len = (n); i < i_len; ++i)
      if (bracket[i] == ')' && stmin.query(0, i) >= 0 &&
          stmin.query(i, n) >= -2)
        ++ans;
  }
  cout << ans << endl;
}

```