#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
char str[2000020];
int s[2000020];
int R[2000020];
int n;
int san[2000020], cnt;
int mi[2000020];
int id[2000020];
int sum[2000020];
struct query1 {
  int l, r, x, v;
  query1() {}
  query1(int l, int r, int x, int v) : l(l), r(r), x(x), v(v) {}
  bool operator<(const query1 &b) const { return x > b.x; }
} b[2000020];
int q1;
struct sam {
  int ch[2000020][2], par[2000020], val[2000020], rr[2000020];
  int tot, lst;
  int num[2000020], topo[2000020];
  int creat(int v) {
    int k = ++tot;
    ch[k][0] = ch[k][1] = par[k] = 0;
    val[k] = v;
    rr[k] = 0;
    return k;
  }
  void init() {
    tot = 0;
    lst = creat(0);
  }
  void extend(int c, int r) {
    int p = lst;
    int np = creat(val[p] + 1);
    rr[np] = r;
    while (p && ch[p][c] == 0) ch[p][c] = np, p = par[p];
    if (!p)
      par[np] = 1;
    else {
      int q = ch[p][c];
      if (val[q] == val[p] + 1)
        par[np] = q;
      else {
        int nq = creat(val[p] + 1);
        memcpy(ch[nq], ch[q], sizeof ch[q]);
        par[nq] = par[q];
        par[q] = par[np] = nq;
        while (p && ch[p][c] == q) ch[p][c] = nq, p = par[p];
      }
    }
    lst = np;
  }
  void get_rr() {
    for (int i = 0; i <= tot; ++i) num[i] = 0;
    for (int i = 1; i <= tot; ++i) num[val[i]]++;
    for (int i = 1; i <= tot; ++i) num[i] += num[i - 1];
    for (int i = tot; i >= 1; --i) topo[num[val[i]]--] = i;
    for (int i = tot; i >= 2; --i) {
      int u = topo[i];
      rr[par[u]] = max(rr[par[u]], rr[u]);
    }
  }
  void get_query1() {
    q1 = 0;
    for (int i = 2; i <= tot; ++i) {
      b[++q1] = query1(rr[i] - val[i] + 1, rr[i] - (val[par[i]] + 1) + 1, rr[i],
                       s[rr[i]]);
    }
  }
} s_auto;
struct query2 {
  int type, l, r, v, t;
  query2() {}
  query2(int type, int l, int r, int v, int t)
      : type(type), l(l), r(r), v(v), t(t) {}
  bool operator<(const query2 &b) const {
    if (v != b.v) return v < b.v;
    return t < b.t;
  }
} c[2000020];
int q2;
int haxi(int x) { return lower_bound(san + 1, san + cnt + 1, x) - san; }
void bit_update(int x, int v) {
  while (x <= cnt) {
    mi[x] = min(mi[x], v);
    x += x & -x;
  }
}
int bit_query(int x) {
  int ret = 0x3f3f3f3f;
  while (x) {
    ret = min(ret, mi[x]);
    x -= x & -x;
  }
  return ret;
}
void get_R() {
  cnt = 0;
  for (int i = 0; i <= n; ++i) san[++cnt] = s[i];
  sort(san + 1, san + cnt + 1);
  cnt = unique(san + 1, san + cnt + 1) - san - 1;
  for (int i = 1; i <= cnt; ++i) mi[i] = 0x3f3f3f3f;
  for (int i = n; i >= 1; --i) {
    int p = haxi(s[i]);
    bit_update(p, i);
    p = haxi(s[i - 1]);
    int tmp_id = bit_query(p - 1);
    if (tmp_id != 0x3f3f3f3f)
      R[i] = tmp_id - 1;
    else
      R[i] = n;
  }
}
bool cmp_by_R(int i, int j) { return R[i] > R[j]; }
void get_query2() {
  int j = 1;
  q2 = 0;
  int tid = 0;
  for (int i = 1; i <= q1; ++i) {
    while (j <= n) {
      int u = id[j];
      if (R[u] >= b[i].x) {
        c[++q2] = query2(0, u, -1, s[u - 1], ++tid);
        ++j;
      } else
        break;
    }
    c[++q2] = query2(2, b[i].l, b[i].r, s[b[i].x], ++tid);
  }
}
int query_sum(int x) {
  int ret = 0;
  while (x) {
    ret += sum[x];
    x -= x & -x;
  }
  return ret;
}
void add(int x, int v) {
  while (x <= n) {
    sum[x] += v;
    x += x & -x;
  }
}
int main() {
  scanf("%d", &n);
  scanf("%s", str + 1);
  for (int i = 1; i <= n; ++i) {
    if (str[i] == '(')
      s[i] = s[i - 1] + 1;
    else
      s[i] = s[i - 1] - 1;
  }
  get_R();
  s_auto.init();
  for (int i = 1; i <= n; ++i) {
    int c;
    if (str[i] == '(')
      c = 0;
    else
      c = 1;
    s_auto.extend(c, i);
  }
  s_auto.get_rr();
  s_auto.get_query1();
  sort(b + 1, b + q1 + 1);
  for (int i = 1; i <= n; ++i) id[i] = i;
  sort(id + 1, id + n + 1, cmp_by_R);
  get_query2();
  long long ans = 0;
  sort(c + 1, c + q2 + 1);
  for (int i = 1; i <= q2; ++i) {
    int j = i;
    while (j <= q2 && c[j].v == c[i].v) ++j;
    --j;
    for (int k = i; k <= j; ++k) {
      if (c[k].type == 0)
        add(c[k].l, 1);
      else
        ans += query_sum(c[k].r) - query_sum(c[k].l - 1);
    }
    for (int k = i; k <= j; ++k) {
      if (c[k].type == 0) add(c[k].l, -1);
    }
    i = j;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
char str[2000020];
int s[2000020];
int R[2000020];
int n;
int san[2000020], cnt;
int mi[2000020];
int id[2000020];
int sum[2000020];
struct query1 {
  int l, r, x, v;
  query1() {}
  query1(int l, int r, int x, int v) : l(l), r(r), x(x), v(v) {}
  bool operator<(const query1 &b) const { return x > b.x; }
} b[2000020];
int q1;
struct sam {
  int ch[2000020][2], par[2000020], val[2000020], rr[2000020];
  int tot, lst;
  int num[2000020], topo[2000020];
  int creat(int v) {
    int k = ++tot;
    ch[k][0] = ch[k][1] = par[k] = 0;
    val[k] = v;
    rr[k] = 0;
    return k;
  }
  void init() {
    tot = 0;
    lst = creat(0);
  }
  void extend(int c, int r) {
    int p = lst;
    int np = creat(val[p] + 1);
    rr[np] = r;
    while (p && ch[p][c] == 0) ch[p][c] = np, p = par[p];
    if (!p)
      par[np] = 1;
    else {
      int q = ch[p][c];
      if (val[q] == val[p] + 1)
        par[np] = q;
      else {
        int nq = creat(val[p] + 1);
        memcpy(ch[nq], ch[q], sizeof ch[q]);
        par[nq] = par[q];
        par[q] = par[np] = nq;
        while (p && ch[p][c] == q) ch[p][c] = nq, p = par[p];
      }
    }
    lst = np;
  }
  void get_rr() {
    for (int i = 0; i <= tot; ++i) num[i] = 0;
    for (int i = 1; i <= tot; ++i) num[val[i]]++;
    for (int i = 1; i <= tot; ++i) num[i] += num[i - 1];
    for (int i = tot; i >= 1; --i) topo[num[val[i]]--] = i;
    for (int i = tot; i >= 2; --i) {
      int u = topo[i];
      rr[par[u]] = max(rr[par[u]], rr[u]);
    }
  }
  void get_query1() {
    q1 = 0;
    for (int i = 2; i <= tot; ++i) {
      b[++q1] = query1(rr[i] - val[i] + 1, rr[i] - (val[par[i]] + 1) + 1, rr[i],
                       s[rr[i]]);
    }
  }
} s_auto;
struct query2 {
  int type, l, r, v, t;
  query2() {}
  query2(int type, int l, int r, int v, int t)
      : type(type), l(l), r(r), v(v), t(t) {}
  bool operator<(const query2 &b) const {
    if (v != b.v) return v < b.v;
    return t < b.t;
  }
} c[2000020];
int q2;
int haxi(int x) { return lower_bound(san + 1, san + cnt + 1, x) - san; }
void bit_update(int x, int v) {
  while (x <= cnt) {
    mi[x] = min(mi[x], v);
    x += x & -x;
  }
}
int bit_query(int x) {
  int ret = 0x3f3f3f3f;
  while (x) {
    ret = min(ret, mi[x]);
    x -= x & -x;
  }
  return ret;
}
void get_R() {
  cnt = 0;
  for (int i = 0; i <= n; ++i) san[++cnt] = s[i];
  sort(san + 1, san + cnt + 1);
  cnt = unique(san + 1, san + cnt + 1) - san - 1;
  for (int i = 1; i <= cnt; ++i) mi[i] = 0x3f3f3f3f;
  for (int i = n; i >= 1; --i) {
    int p = haxi(s[i]);
    bit_update(p, i);
    p = haxi(s[i - 1]);
    int tmp_id = bit_query(p - 1);
    if (tmp_id != 0x3f3f3f3f)
      R[i] = tmp_id - 1;
    else
      R[i] = n;
  }
}
bool cmp_by_R(int i, int j) { return R[i] > R[j]; }
void get_query2() {
  int j = 1;
  q2 = 0;
  int tid = 0;
  for (int i = 1; i <= q1; ++i) {
    while (j <= n) {
      int u = id[j];
      if (R[u] >= b[i].x) {
        c[++q2] = query2(0, u, -1, s[u - 1], ++tid);
        ++j;
      } else
        break;
    }
    c[++q2] = query2(2, b[i].l, b[i].r, s[b[i].x], ++tid);
  }
}
int query_sum(int x) {
  int ret = 0;
  while (x) {
    ret += sum[x];
    x -= x & -x;
  }
  return ret;
}
void add(int x, int v) {
  while (x <= n) {
    sum[x] += v;
    x += x & -x;
  }
}
int main() {
  scanf("%d", &n);
  scanf("%s", str + 1);
  for (int i = 1; i <= n; ++i) {
    if (str[i] == '(')
      s[i] = s[i - 1] + 1;
    else
      s[i] = s[i - 1] - 1;
  }
  get_R();
  s_auto.init();
  for (int i = 1; i <= n; ++i) {
    int c;
    if (str[i] == '(')
      c = 0;
    else
      c = 1;
    s_auto.extend(c, i);
  }
  s_auto.get_rr();
  s_auto.get_query1();
  sort(b + 1, b + q1 + 1);
  for (int i = 1; i <= n; ++i) id[i] = i;
  sort(id + 1, id + n + 1, cmp_by_R);
  get_query2();
  long long ans = 0;
  sort(c + 1, c + q2 + 1);
  for (int i = 1; i <= q2; ++i) {
    int j = i;
    while (j <= q2 && c[j].v == c[i].v) ++j;
    --j;
    for (int k = i; k <= j; ++k) {
      if (c[k].type == 0)
        add(c[k].l, 1);
      else
        ans += query_sum(c[k].r) - query_sum(c[k].l - 1);
    }
    for (int k = i; k <= j; ++k) {
      if (c[k].type == 0) add(c[k].l, -1);
    }
    i = j;
  }
  cout << ans << endl;
  return 0;
}

```