#include <bits/stdc++.h>
using namespace std;
const char IO_MODE = 0;
inline long long ReadInt() {
  long long x = 0, s = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') s = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return s * x;
}
inline void WriteInt(long long x) {
  char c[20];
  if (!x) {
    putchar('0');
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  int i = 0;
  while (x > 0) c[++i] = x % 10, x /= 10;
  while (i) putchar(c[i--] + 48);
}
template <typename T>
inline void out(T x) {
  if (IO_MODE & 1)
    WriteInt(x);
  else if (typeid(x) == typeid(int))
    printf("%i", x);
  else
    printf("%lld", (long long)x);
}
template <typename T, typename... Args>
inline void out(T x, Args... args) {
  out(x);
  putc(' ', stdout);
  out(args...);
}
template <typename T>
inline void in(T& x) {
  if (IO_MODE & 2)
    x = ReadInt();
  else if (typeid(x) == typeid(int))
    scanf("%i", &x);
  else if (typeid(x) == typeid(long long))
    scanf("%lld", &x);
}
template <typename T, typename... Args>
inline void in(T& x, Args&... args) {
  in(x);
  in(args...);
}
int aa, bb, cc, dd, ee, ff, gg, hh, ii, jj, kk, mm, nn, oo, pp, qq, rr, ss, tt,
    uu, vv, ww, xx, yy, zz;
int tc;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
char s[500100];
int n, A[500100];
long long ans;
struct SuffixArray {
  int suf[500100], cnt[500100], rnk[500100], lcp[500100];
  void build(int* s, int n) {
    if (n <= 1) return;
    int m = max(n, 256);
    Skew(s, suf, n, m);
  }
  inline bool leq(int a1, int a2, int b1, int b2) {
    return a1 < b1 || a1 == b1 && a2 <= b2;
  }
  inline bool leq(int a1, int a2, int a3, int b1, int b2, int b3) {
    return a1 < b1 || a1 == b1 && leq(a2, a3, b2, b3);
  }
  void radixPass(int* a, int* b, int* c, int n, int K) {
    memset(cnt, 0, ++K * sizeof(int));
    for (int i = 0; i < n; i++) cnt[c[a[i]]]++;
    for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i--;) b[--cnt[c[a[i]]]] = a[i];
  }
  void Skew(int* s, int* SA, int n, int K) {
    int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;
    int* s12 = new int[n02 + 3];
    s12[n02] = s12[n02 + 1] = s12[n02 + 2] = 0;
    int* SA12 = new int[n02 + 3];
    SA12[n02] = SA12[n02 + 1] = SA12[n02 + 2] = 0;
    int* s0 = new int[n0];
    int* SA0 = new int[n0];
    for (int i = 0, j = 0; i < n + (n0 - n1); i++)
      if (i % 3) s12[j++] = i;
    radixPass(s12, SA12, s + 2, n02, K);
    radixPass(SA12, s12, s + 1, n02, K);
    radixPass(s12, SA12, s, n02, K);
    int name = 0, c0 = -1, c1 = -1, c2 = -1;
    for (int i = 0; i < n02; i++) {
      if (s[SA12[i]] != c0 || s[SA12[i] + 1] != c1 || s[SA12[i] + 2] != c2)
        name++;
      c0 = s[SA12[i]];
      c1 = s[SA12[i] + 1];
      c2 = s[SA12[i] + 2];
      if (SA12[i] % 3 == 1)
        s12[SA12[i] / 3] = name;
      else
        s12[SA12[i] / 3 + n0] = name;
    }
    if (name < n02) {
      Skew(s12, SA12, n02, name);
      for (int i = 0; i < n02; i++) s12[SA12[i]] = i + 1;
    } else
      for (int i = 0; i < n02; i++) SA12[s12[i] - 1] = i;
    for (int i = 0, j = 0; i < n02; i++)
      if (SA12[i] < n0) s0[j++] = 3 * SA12[i];
    radixPass(s0, SA0, s, n0, K);
    for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
      int i = (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2);
      int j = SA0[p];
      if (SA12[t] < n0 ? leq(s[i], s12[SA12[t] + n0], s[j], s12[j / 3])
                       : leq(s[i], s[i + 1], s12[SA12[t] - n0 + 1], s[j],
                             s[j + 1], s12[j / 3 + n0])) {
        SA[k] = i;
        t++;
        if (t == n02)
          for (k++; p < n0; p++, k++) SA[k] = SA0[p];
      } else {
        SA[k] = j;
        p++;
        if (p == n0)
          for (k++; t < n02; t++, k++)
            SA[k] = (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2);
      }
    }
    delete[] s12;
    delete[] SA12;
    delete[] SA0;
    delete[] s0;
  }
  void KasaiLCP(int* s, int n) {
    int k = 0;
    for (int i = 0; i < n; i++) rnk[suf[i]] = i;
    for (int i = 0; i < n; i++)
      if (rnk[i] == n - 1)
        k = 0;
      else {
        int j = suf[rnk[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rnk[i]] = k;
        if (k) k--;
      }
  }
  int& operator[](int i) { return suf[i]; }
} Sa{};
struct SparseTable {
  int n, *A, M[500100][(31 ^ __builtin_clz(500100)) + 1];
  void build(int* _A, int _n) {
    A = _A, n = _n;
    for (int i = 0; i < n; i++) M[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++)
      for (int i = 0; i + (1 << j) - 1 < n; i++)
        M[i][j] = A[M[i][j - 1]] <= A[M[i + (1 << j - 1)][j - 1]]
                      ? M[i][j - 1]
                      : M[i + (1 << j - 1)][j - 1];
  }
  int inline rmnq(int l, int r) {
    int k = (31 ^ __builtin_clz(r - l + 1));
    return A[M[l][k]] <= A[M[r - (1 << k) + 1][k]] ? M[l][k]
                                                   : M[r - (1 << k) + 1][k];
  }
} St;
struct ValidSubstrCounter {
  vector<pair<int, int> > G[500100 << 1];
  vector<pair<int, int> >* g = G + 500100;
  int Bal[500100], Neg[500100], L[500100 << 1], *last = L + 500100;
  void build() {
    memset(last, 0, sizeof last);
    int bal = 0;
    for (int i = 0; i < n; i++) {
      bal += s[i] == '(' ? +1 : -1;
      g[bal].emplace_back(last[bal], i);
      if (s[i] == ')') last[bal + 1]++;
      Neg[i] = last[Bal[i] = bal];
    }
  }
  int qry(int l, int r) {
    if (l >= r || s[l] == ')') return 0;
    int c = l ? Neg[l - 1] : 0;
    int b = l ? Bal[l - 1] : 0;
    return upper_bound(g[b].begin(), g[b].end(), make_pair(c, r)) -
           lower_bound(g[b].begin(), g[b].end(), make_pair(c, l));
  }
} Vsc;
void DivConq(int L, int R, int pre) {
  if (L > R) return;
  int mid = L == R ? 0 : St.rmnq(L, R - 1);
  int cur = L == R ? n - Sa[L] : Sa.lcp[mid];
  int aa = Vsc.qry(Sa[L], Sa[L] + cur - 1) - Vsc.qry(Sa[L], Sa[L] + pre - 1);
  ans += aa;
  if (L == R) return;
  DivConq(L, mid, cur);
  DivConq(mid + 1, R, cur);
}
int32_t main() {
  n = ReadInt();
  scanf("%s", s);
  transform(s, s + n, A, [](char c) -> int { return c; });
  Sa.build(A, n);
  Sa.KasaiLCP(A, n);
  St.build(Sa.lcp, n - 1);
  Vsc.build();
  DivConq(0, n - 1, 0);
  cout << ans << endl;
}

### Prompt

Please formulate a cpp solution to the following problem:

Alex was programming while Valentina (his toddler daughter) got there and started asking many questions about the round brackets (or parenthesis) in the code. He explained her a bit and when she got it he gave her a task in order to finish his code on time.

For the purpose of this problem we consider only strings consisting of opening and closing round brackets, that is characters '(' and ')'.

The sequence of brackets is called correct if: 

  1. it's empty; 
  2. it's a correct sequence of brackets, enclosed in a pair of opening and closing brackets; 
  3. it's a concatenation of two correct sequences of brackets. 



For example, the sequences "()()" and "((()))(())" are correct, while ")(()", "(((((" and "())" are not.

Alex took a piece of paper, wrote a string s consisting of brackets and asked Valentina to count the number of distinct non-empty substrings of s that are correct sequences of brackets. In other words, her task is to count the number of non-empty correct sequences of brackets that occur in a string s as a substring (don't mix up with subsequences).

When Valentina finished the task, Alex noticed he doesn't know the answer. Help him don't loose face in front of Valentina and solve the problem!

Input

The first line of the input contains an integer n (1 ≤ n ≤ 500 000) — the length of the string s.

The second line contains a string s of length n consisting of only '(' and ')'.

Output

Print the number of distinct non-empty correct sequences that occur in s as substring.

Examples

Input

10
()()()()()


Output

5


Input

7
)(())()


Output

3

Note

In the first sample, there are 5 distinct substrings we should count: "()", "()()", "()()()", "()()()()" and "()()()()()".

In the second sample, there are 3 distinct substrings we should count: "()", "(())" and "(())()".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const char IO_MODE = 0;
inline long long ReadInt() {
  long long x = 0, s = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') s = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return s * x;
}
inline void WriteInt(long long x) {
  char c[20];
  if (!x) {
    putchar('0');
    return;
  }
  if (x < 0) putchar('-'), x = -x;
  int i = 0;
  while (x > 0) c[++i] = x % 10, x /= 10;
  while (i) putchar(c[i--] + 48);
}
template <typename T>
inline void out(T x) {
  if (IO_MODE & 1)
    WriteInt(x);
  else if (typeid(x) == typeid(int))
    printf("%i", x);
  else
    printf("%lld", (long long)x);
}
template <typename T, typename... Args>
inline void out(T x, Args... args) {
  out(x);
  putc(' ', stdout);
  out(args...);
}
template <typename T>
inline void in(T& x) {
  if (IO_MODE & 2)
    x = ReadInt();
  else if (typeid(x) == typeid(int))
    scanf("%i", &x);
  else if (typeid(x) == typeid(long long))
    scanf("%lld", &x);
}
template <typename T, typename... Args>
inline void in(T& x, Args&... args) {
  in(x);
  in(args...);
}
int aa, bb, cc, dd, ee, ff, gg, hh, ii, jj, kk, mm, nn, oo, pp, qq, rr, ss, tt,
    uu, vv, ww, xx, yy, zz;
int tc;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
char s[500100];
int n, A[500100];
long long ans;
struct SuffixArray {
  int suf[500100], cnt[500100], rnk[500100], lcp[500100];
  void build(int* s, int n) {
    if (n <= 1) return;
    int m = max(n, 256);
    Skew(s, suf, n, m);
  }
  inline bool leq(int a1, int a2, int b1, int b2) {
    return a1 < b1 || a1 == b1 && a2 <= b2;
  }
  inline bool leq(int a1, int a2, int a3, int b1, int b2, int b3) {
    return a1 < b1 || a1 == b1 && leq(a2, a3, b2, b3);
  }
  void radixPass(int* a, int* b, int* c, int n, int K) {
    memset(cnt, 0, ++K * sizeof(int));
    for (int i = 0; i < n; i++) cnt[c[a[i]]]++;
    for (int i = 1; i < K; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i--;) b[--cnt[c[a[i]]]] = a[i];
  }
  void Skew(int* s, int* SA, int n, int K) {
    int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n02 = n0 + n2;
    int* s12 = new int[n02 + 3];
    s12[n02] = s12[n02 + 1] = s12[n02 + 2] = 0;
    int* SA12 = new int[n02 + 3];
    SA12[n02] = SA12[n02 + 1] = SA12[n02 + 2] = 0;
    int* s0 = new int[n0];
    int* SA0 = new int[n0];
    for (int i = 0, j = 0; i < n + (n0 - n1); i++)
      if (i % 3) s12[j++] = i;
    radixPass(s12, SA12, s + 2, n02, K);
    radixPass(SA12, s12, s + 1, n02, K);
    radixPass(s12, SA12, s, n02, K);
    int name = 0, c0 = -1, c1 = -1, c2 = -1;
    for (int i = 0; i < n02; i++) {
      if (s[SA12[i]] != c0 || s[SA12[i] + 1] != c1 || s[SA12[i] + 2] != c2)
        name++;
      c0 = s[SA12[i]];
      c1 = s[SA12[i] + 1];
      c2 = s[SA12[i] + 2];
      if (SA12[i] % 3 == 1)
        s12[SA12[i] / 3] = name;
      else
        s12[SA12[i] / 3 + n0] = name;
    }
    if (name < n02) {
      Skew(s12, SA12, n02, name);
      for (int i = 0; i < n02; i++) s12[SA12[i]] = i + 1;
    } else
      for (int i = 0; i < n02; i++) SA12[s12[i] - 1] = i;
    for (int i = 0, j = 0; i < n02; i++)
      if (SA12[i] < n0) s0[j++] = 3 * SA12[i];
    radixPass(s0, SA0, s, n0, K);
    for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
      int i = (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2);
      int j = SA0[p];
      if (SA12[t] < n0 ? leq(s[i], s12[SA12[t] + n0], s[j], s12[j / 3])
                       : leq(s[i], s[i + 1], s12[SA12[t] - n0 + 1], s[j],
                             s[j + 1], s12[j / 3 + n0])) {
        SA[k] = i;
        t++;
        if (t == n02)
          for (k++; p < n0; p++, k++) SA[k] = SA0[p];
      } else {
        SA[k] = j;
        p++;
        if (p == n0)
          for (k++; t < n02; t++, k++)
            SA[k] = (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2);
      }
    }
    delete[] s12;
    delete[] SA12;
    delete[] SA0;
    delete[] s0;
  }
  void KasaiLCP(int* s, int n) {
    int k = 0;
    for (int i = 0; i < n; i++) rnk[suf[i]] = i;
    for (int i = 0; i < n; i++)
      if (rnk[i] == n - 1)
        k = 0;
      else {
        int j = suf[rnk[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rnk[i]] = k;
        if (k) k--;
      }
  }
  int& operator[](int i) { return suf[i]; }
} Sa{};
struct SparseTable {
  int n, *A, M[500100][(31 ^ __builtin_clz(500100)) + 1];
  void build(int* _A, int _n) {
    A = _A, n = _n;
    for (int i = 0; i < n; i++) M[i][0] = i;
    for (int j = 1; (1 << j) <= n; j++)
      for (int i = 0; i + (1 << j) - 1 < n; i++)
        M[i][j] = A[M[i][j - 1]] <= A[M[i + (1 << j - 1)][j - 1]]
                      ? M[i][j - 1]
                      : M[i + (1 << j - 1)][j - 1];
  }
  int inline rmnq(int l, int r) {
    int k = (31 ^ __builtin_clz(r - l + 1));
    return A[M[l][k]] <= A[M[r - (1 << k) + 1][k]] ? M[l][k]
                                                   : M[r - (1 << k) + 1][k];
  }
} St;
struct ValidSubstrCounter {
  vector<pair<int, int> > G[500100 << 1];
  vector<pair<int, int> >* g = G + 500100;
  int Bal[500100], Neg[500100], L[500100 << 1], *last = L + 500100;
  void build() {
    memset(last, 0, sizeof last);
    int bal = 0;
    for (int i = 0; i < n; i++) {
      bal += s[i] == '(' ? +1 : -1;
      g[bal].emplace_back(last[bal], i);
      if (s[i] == ')') last[bal + 1]++;
      Neg[i] = last[Bal[i] = bal];
    }
  }
  int qry(int l, int r) {
    if (l >= r || s[l] == ')') return 0;
    int c = l ? Neg[l - 1] : 0;
    int b = l ? Bal[l - 1] : 0;
    return upper_bound(g[b].begin(), g[b].end(), make_pair(c, r)) -
           lower_bound(g[b].begin(), g[b].end(), make_pair(c, l));
  }
} Vsc;
void DivConq(int L, int R, int pre) {
  if (L > R) return;
  int mid = L == R ? 0 : St.rmnq(L, R - 1);
  int cur = L == R ? n - Sa[L] : Sa.lcp[mid];
  int aa = Vsc.qry(Sa[L], Sa[L] + cur - 1) - Vsc.qry(Sa[L], Sa[L] + pre - 1);
  ans += aa;
  if (L == R) return;
  DivConq(L, mid, cur);
  DivConq(mid + 1, R, cur);
}
int32_t main() {
  n = ReadInt();
  scanf("%s", s);
  transform(s, s + n, A, [](char c) -> int { return c; });
  Sa.build(A, n);
  Sa.KasaiLCP(A, n);
  St.build(Sa.lcp, n - 1);
  Vsc.build();
  DivConq(0, n - 1, 0);
  cout << ans << endl;
}

```