#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
template <typename T>
T fac(T a) {
  return a ? a * fac(a - 1) : 1;
}
template <typename T>
T power(T a, int p) {
  return !p ? 1 : (p & 1 ? a * power(a, p - 1) : power(a * a, p >> 1));
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
T lcm(T a, T b) {
  return b / gcd(a, b) * a;
}
template <typename T>
T next() {
  T _;
  cin >> _;
  return _;
}
template <>
int next<int>() {
  int _;
  scanf("%d", &_);
  return _;
}
template <>
double next<double>() {
  double _;
  scanf("%lf", &_);
  return _;
}
template <>
long long next<long long>() {
  long long _;
  scanf("%lld", &_);
  return _;
}
template <typename E>
vector<E> next(int n) {
  vector<E> res(n);
  for (int i = 0; i < n; i++) res[i] = next<E>();
  return res;
}
template <class C, class E>
int count(const C &c, const E &e) {
  return count(c.begin(), c.end(), e);
}
template <class E>
bool has(const vector<E> &c, const E &e) {
  return find(c.begin(), c.end(), e) != c.end();
}
template <class E>
int find(const vector<E> &c, const E &e) {
  return find(c.begin(), c.end(), e) - c.begin();
}
template <class E>
bool binary_has(const vector<E> &c, const E &e) {
  return binary_search(c.begin(), c.end(), e);
}
template <class E>
int binary_find(const vector<E> &c, const E &e) {
  return lower_bound(c.begin(), c.end(), e) - c.begin();
}
template <typename T>
T dist2(T i1, T j1, T i2, T j2) {
  return (i1 - i2) * (i1 - i2) + (j1 - j2) * (j1 - j2);
}
bool ok(int i, int j, int n, int m) {
  return 0 <= i && i < n && 0 <= j && j < m;
}
const double EPS = 1e-9;
const double PI = acos(-1);
bool LE(double a, double b) { return b - a > -EPS; }
bool BE(double a, double b) { return a - b > -EPS; }
bool EQ(double a, double b) { return fabs(a - b) < EPS; }
bool LESS(double a, double b) { return b - a > EPS; }
bool BIGG(double a, double b) { return a - b > EPS; }
char s[1001000];
int main() {
  int n = next<int>();
  scanf("%s", s);
  vector<int> v(n);
  int balanse = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(')
      balanse++;
    else
      balanse--;
    v[i] = balanse;
  }
  vector<int> minr(v);
  for (int i = n - 2; i >= 0; i--) {
    minr[i] = min(minr[i + 1], minr[i]);
  }
  vector<int> minl(v);
  for (int i = 1; i < n; i++) {
    minl[i] = min(minl[i - 1], minl[i]);
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(' && v.back() == 2 && minr[i] == 2 &&
        (i == 0 || minl[i - 1] >= 0))
      res++;
    if (s[i] == ')' && v.back() == -2 && minr[i] == -2 &&
        (i == 0 || minl[i - 1] >= 0))
      res++;
  }
  cout << res << endl;
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
#pragma comment(linker, "/STACK:16777216")
template <typename T>
T fac(T a) {
  return a ? a * fac(a - 1) : 1;
}
template <typename T>
T power(T a, int p) {
  return !p ? 1 : (p & 1 ? a * power(a, p - 1) : power(a * a, p >> 1));
}
template <typename T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
T lcm(T a, T b) {
  return b / gcd(a, b) * a;
}
template <typename T>
T next() {
  T _;
  cin >> _;
  return _;
}
template <>
int next<int>() {
  int _;
  scanf("%d", &_);
  return _;
}
template <>
double next<double>() {
  double _;
  scanf("%lf", &_);
  return _;
}
template <>
long long next<long long>() {
  long long _;
  scanf("%lld", &_);
  return _;
}
template <typename E>
vector<E> next(int n) {
  vector<E> res(n);
  for (int i = 0; i < n; i++) res[i] = next<E>();
  return res;
}
template <class C, class E>
int count(const C &c, const E &e) {
  return count(c.begin(), c.end(), e);
}
template <class E>
bool has(const vector<E> &c, const E &e) {
  return find(c.begin(), c.end(), e) != c.end();
}
template <class E>
int find(const vector<E> &c, const E &e) {
  return find(c.begin(), c.end(), e) - c.begin();
}
template <class E>
bool binary_has(const vector<E> &c, const E &e) {
  return binary_search(c.begin(), c.end(), e);
}
template <class E>
int binary_find(const vector<E> &c, const E &e) {
  return lower_bound(c.begin(), c.end(), e) - c.begin();
}
template <typename T>
T dist2(T i1, T j1, T i2, T j2) {
  return (i1 - i2) * (i1 - i2) + (j1 - j2) * (j1 - j2);
}
bool ok(int i, int j, int n, int m) {
  return 0 <= i && i < n && 0 <= j && j < m;
}
const double EPS = 1e-9;
const double PI = acos(-1);
bool LE(double a, double b) { return b - a > -EPS; }
bool BE(double a, double b) { return a - b > -EPS; }
bool EQ(double a, double b) { return fabs(a - b) < EPS; }
bool LESS(double a, double b) { return b - a > EPS; }
bool BIGG(double a, double b) { return a - b > EPS; }
char s[1001000];
int main() {
  int n = next<int>();
  scanf("%s", s);
  vector<int> v(n);
  int balanse = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(')
      balanse++;
    else
      balanse--;
    v[i] = balanse;
  }
  vector<int> minr(v);
  for (int i = n - 2; i >= 0; i--) {
    minr[i] = min(minr[i + 1], minr[i]);
  }
  vector<int> minl(v);
  for (int i = 1; i < n; i++) {
    minl[i] = min(minl[i - 1], minl[i]);
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(' && v.back() == 2 && minr[i] == 2 &&
        (i == 0 || minl[i - 1] >= 0))
      res++;
    if (s[i] == ')' && v.back() == -2 && minr[i] == -2 &&
        (i == 0 || minl[i - 1] >= 0))
      res++;
  }
  cout << res << endl;
  return 0;
}

```