#include <bits/stdc++.h>
using namespace std;
long long int MOD = 1e9 + 7;
long long int INF = 1e18;
long long int visited[5100];
void dfs(vector<long long int> adj[], int i) {
  visited[i] = true;
  int j;
  for (auto j : adj[i]) {
    if (!visited[j]) {
      dfs(adj, j);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int i, j, k = 0, l = 0, r = 0, m = 0, n, p = 0, cnt = 0, cnt1 = 0,
                      x, y, z = 0, a, b, low, mid, high, ans = 0, maxi = 0,
                      mini = INF, t;
  string s, s1;
  cin >> n;
  pair<long long int, long long int> pre[n + 1];
  pair<long long int, long long int> suf[n + 2];
  stack<char> st;
  stack<char> sc;
  cin >> s;
  p = 1;
  pre[0] = {0, 1};
  suf[n + 1] = {0, 1};
  for (i = 0; i < n; i++) {
    if (s[i] == '(') {
      st.push('(');
      l = st.size();
      pre[i + 1] = {l, p};
    } else {
      if (!st.empty() && st.top() == '(') {
        st.pop();
      } else {
        st.push(')');
        p = 0;
      }
      l = st.size();
      pre[i + 1] = {l, p};
    }
  }
  p = 1;
  for (i = n - 1; i >= 0; i--) {
    if (s[i] == ')') {
      sc.push(')');
      l = sc.size();
      suf[i + 1] = {l, p};
    } else {
      if (!sc.empty() && sc.top() == ')') {
        sc.pop();
      } else {
        sc.push('(');
        p = 0;
      }
      l = sc.size();
      suf[i + 1] = {l, p};
    }
  }
  for (i = 0; i < n; i++) {
    if (s[i] == '(') {
      a = pre[i + 1].first;
      b = pre[i].second;
      if (b == 1) {
        a = a - 2;
        k = suf[i + 2].second;
        l = suf[i + 2].first;
        if (k == 1 && l == a) {
          cnt++;
        }
      }
    } else {
      k = suf[i + 2].second;
      l = suf[i + 2].first;
      if (pre[i].second == 1) {
        if (pre[i + 1].second == 0) {
          a = pre[i + 1].first;
        } else {
          a = pre[i + 1].first + 2;
        }
        if (k == 1 && l == a) cnt++;
      }
    }
  }
  cout << cnt << 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;
long long int MOD = 1e9 + 7;
long long int INF = 1e18;
long long int visited[5100];
void dfs(vector<long long int> adj[], int i) {
  visited[i] = true;
  int j;
  for (auto j : adj[i]) {
    if (!visited[j]) {
      dfs(adj, j);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int i, j, k = 0, l = 0, r = 0, m = 0, n, p = 0, cnt = 0, cnt1 = 0,
                      x, y, z = 0, a, b, low, mid, high, ans = 0, maxi = 0,
                      mini = INF, t;
  string s, s1;
  cin >> n;
  pair<long long int, long long int> pre[n + 1];
  pair<long long int, long long int> suf[n + 2];
  stack<char> st;
  stack<char> sc;
  cin >> s;
  p = 1;
  pre[0] = {0, 1};
  suf[n + 1] = {0, 1};
  for (i = 0; i < n; i++) {
    if (s[i] == '(') {
      st.push('(');
      l = st.size();
      pre[i + 1] = {l, p};
    } else {
      if (!st.empty() && st.top() == '(') {
        st.pop();
      } else {
        st.push(')');
        p = 0;
      }
      l = st.size();
      pre[i + 1] = {l, p};
    }
  }
  p = 1;
  for (i = n - 1; i >= 0; i--) {
    if (s[i] == ')') {
      sc.push(')');
      l = sc.size();
      suf[i + 1] = {l, p};
    } else {
      if (!sc.empty() && sc.top() == ')') {
        sc.pop();
      } else {
        sc.push('(');
        p = 0;
      }
      l = sc.size();
      suf[i + 1] = {l, p};
    }
  }
  for (i = 0; i < n; i++) {
    if (s[i] == '(') {
      a = pre[i + 1].first;
      b = pre[i].second;
      if (b == 1) {
        a = a - 2;
        k = suf[i + 2].second;
        l = suf[i + 2].first;
        if (k == 1 && l == a) {
          cnt++;
        }
      }
    } else {
      k = suf[i + 2].second;
      l = suf[i + 2].first;
      if (pre[i].second == 1) {
        if (pre[i + 1].second == 0) {
          a = pre[i + 1].first;
        } else {
          a = pre[i + 1].first + 2;
        }
        if (k == 1 && l == a) cnt++;
      }
    }
  }
  cout << cnt << endl;
}

```