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>
using namespace std;
long double pi = 3.14159265358979323846;
vector<long long> al[500005];
long long vis[500005], color[500005];
long long I[101][101];
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
bool isPrime(int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long bpow(long long n, long long po) {
  long long res = 1;
  while (po > 0) {
    if (po % 2) {
      res = (res * n) % 1000000007;
      po--;
    } else {
      n = (n * n) % 1000000007;
      po /= 2;
    }
  }
  return res;
}
void swap(long long *a, long long *b) {
  long long temp = *a;
  *a = *b;
  *b = temp;
}
long long fact(long long n) {
  if ((n == 0) || (n == 1))
    return 1;
  else
    return n * fact(n - 1);
}
long long modInverse(long long n, long long p) { return bpow(n, p - 2); }
long long fac[300001];
long long nCr(long long n, long long r) {
  if (r == 0) return 1;
  return (fac[n] * modInverse(fac[r], 1000000007) % 1000000007 *
          modInverse(fac[n - r], 1000000007) % 1000000007) %
         1000000007;
}
void mmul(long long A[][101], long long B[][101], long long dim) {
  long long res[dim][dim];
  for (long long i = 0; i < dim; i++)
    for (long long j = 0; j < dim; j++) {
      res[i][j] = 0;
      for (long long k = 0; k < dim; k++)
        res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % 1000000007;
    }
  for (long long i = 0; i < dim; i++)
    for (long long j = 0; j < dim; j++) A[i][j] = res[i][j];
}
void mpow(long long A[][101], long long dim, long long po) {
  for (long long i = 0; i < dim; i++)
    for (long long j = 0; j < dim; j++) {
      if (i == j)
        I[i][j] = 1;
      else
        I[i][j] = 0;
    }
  while (po > 0) {
    if (po % 2 == 1) {
      mmul(I, A, dim);
      po--;
    } else {
      mmul(A, A, dim);
      po /= 2;
    }
  }
  for (long long i = 0; i < dim; i++)
    for (long long j = 0; j < dim; j++) A[i][j] = I[i][j];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long testcases = 1;
  while (testcases--) {
    long long n, ans = 0;
    cin >> n;
    string s;
    cin >> s;
    long long a[n], cc = 0;
    for (long long i = 0; i < n; i++) {
      if (s[i] == '(')
        cc++;
      else
        cc--;
      a[i] = cc;
    }
    if (a[n - 1] == 2) {
      long long mm = a[n - 1];
      for (long long i = n - 1; i >= 0; i--) {
        mm = min(mm, a[i]);
        if (mm < 2) break;
        if (s[i] == '(') ans++;
      }
      for (long long i = 0; i < n; i++)
        if (a[i] < 0) ans = 0;
    } else if (a[n - 1] == -2) {
      long long mm = a[0];
      for (long long i = 0; i < n; i++) {
        mm = min(mm, a[i]);
        if (s[i] == ')') ans++;
        if (mm < 0) break;
      }
      for (long long i = 0; i < n; i++)
        if (a[i] < -2) ans = 0;
    }
    cout << ans;
  }
}
