#include <bits/stdc++.h>
using namespace std;
template <typename T>
T In() {
  char ch;
  T n = 0;
  bool ng = false;
  while (1) {
    ch = getchar();
    if (ch == '-') {
      ng = true;
      ch = getchar();
      break;
    }
    if (ch >= '0' && ch <= '9') break;
  }
  while (1) {
    n = n * 10 + (ch - '0');
    ch = getchar();
    if (ch < '0' || ch > '9') break;
  }
  return (ng ? -n : n);
}
template <class T, class first>
inline bool checkbit(T a, first pos) {
  T t = 1;
  return ((a & (t << pos)) > 0);
}
template <class T, class first>
inline T setbit(T a, first pos) {
  T t = 1;
  return (a | (t << pos));
}
template <class T, class first>
inline T resetbit(T a, first pos) {
  T t = 1;
  return (a & (~(t << pos)));
}
template <class T, class first>
inline T togglebit(T a, first pos) {
  T t = 1;
  return (a ^ (t << pos));
}
template <typename T>
T POW(T base, T power) {
  T ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base);
    base = (base * base);
    power >>= 1;
  }
  return ret;
}
template <typename T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <typename T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / GCD(a, b));
}
template <typename T>
T EUCLIDE(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <typename T>
T ABS(T a) {
  if (a < 0)
    return -a;
  else
    return a;
}
long long Bigmod(long long base, long long power, long long _MOD) {
  long long ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base) % _MOD;
    base = (base * base) % _MOD;
    power >>= 1;
  }
  return ret;
}
long long ModInverse(long long number, long long _MOD) {
  return Bigmod(number, _MOD - 2LL, _MOD);
}
template <typename T>
double DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
long long isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
void BINARY(int n) {
  bitset<31> a = n;
  cout << a << endl;
}
void P_ARR(int *ar, int a, int b) {
  if (a > b) swap(a, b);
  if (a <= b) cout << ar[a];
  for (int i = a + 1; i <= b; i++) cout << " " << ar[i];
  cout << endl;
}
template <class T>
inline void make_unique_vec(vector<T> &vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
template <class T>
inline void make_unique_arr(T *ar, int &n) {
  sort(ar + 1, ar + n + 1);
  n = unique(ar + 1, ar + n + 1) - ar - 1;
}
const int N = 500007;
struct SUFFIX_ARRAY {
  int wa[N], wb[N], ws[N], wv[N], r[N];
  int len;
  int rnk[N];
  int height[N];
  int sa[N];
  int cmp(int *ar, int a, int b, int l) {
    return (ar[a] == ar[b]) && (ar[a + l] == ar[b + l]);
  }
  void DA(int n, int m) {
    int i, j, p, *x = wa, *y = wb, *t;
    for (i = 0; i < m; i++) ws[i] = 0;
    for (i = 0; i < n; i++) ws[x[i] = r[i]]++;
    for (i = 1; i < m; i++) ws[i] += ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
      for (p = 0, i = n - j; i < n; i++) y[p++] = i;
      for (i = 0; i < n; i++)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      for (i = 0; i < n; i++) wv[i] = x[y[i]];
      for (i = 0; i < m; i++) ws[i] = 0;
      for (i = 0; i < n; i++) ws[wv[i]]++;
      for (i = 1; i < m; i++) ws[i] += ws[i - 1];
      for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i];
      for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
        x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
  }
  void calheight(int n) {
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rnk[sa[i]] = i;
    for (i = 0; i < n; height[rnk[i++]] = k)
      for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++)
        ;
  }
  void generate(char *s) {
    for (len = 0; s[len]; len++) r[len] = (int)s[len];
    r[len] = 0;
    DA(len + 1, 128);
    calheight(len);
  }
  void print() {
    cout << "length :  " << len << endl;
    cout << "s[n] = '$' " << endl;
    cout << "sorted suffix index(0 based) : " << endl;
    for (int i = 0; i <= len; i++) cout << sa[i] << " , ";
    cout << endl;
    cout << "rank of suffix " << endl;
    for (int i = 0; i <= len; i++) cout << rnk[i] << " , ";
    cout << endl;
    cout << "LCP between i and i-1 " << endl;
    for (int i = 0; i <= len; i++) cout << height[i] << " , ";
    cout << endl;
  }
} SA;
char s[500007];
struct node {
  int sum;
  node *l, *r;
  node() {
    sum = 0;
    l = r = NULL;
  }
};
node tree[500007 * 21];
node *head[500007];
int avail;
node *update(node *pre, int s, int e, int pos) {
  node *ob = &tree[++avail];
  if (pre != NULL) *ob = *pre;
  if (s == e) {
    ob->sum++;
    return ob;
  }
  int mid = (s + e) >> 1;
  if (pos <= mid)
    ob->l = update(ob->l, s, mid, pos);
  else
    ob->r = update(ob->r, mid + 1, e, pos);
  ob->sum = 0;
  if (ob->l != NULL) ob->sum += ob->l->sum;
  if (ob->r != NULL) ob->sum += ob->r->sum;
  return ob;
}
int query(node *ob, int s, int e, int x, int y) {
  if (s > e) return 0;
  if (x > y) return 0;
  if (ob == NULL) return 0;
  if (s == x && e == y) {
    return ob->sum;
  }
  int mid = (s + e) >> 1;
  if (y <= mid)
    return query(ob->l, s, mid, x, y);
  else if (x > mid)
    return query(ob->r, mid + 1, e, x, y);
  else {
    int lt = query(ob->l, s, mid, x, mid);
    int rt = query(ob->r, mid + 1, e, mid + 1, y);
    return (lt + rt);
  }
}
int stk[500007];
int nxt[500007];
int top;
int main() {
  int n;
  scanf("%d", &(n));
  ;
  scanf("%s", s + 1);
  SA.generate(s + 1);
  head[0] = new node();
  head[n + 1] = new node();
  for (int i = n; i >= 1; i--) {
    head[i] = head[n + 1];
    if (s[i] == ')') {
      stk[++top] = i;
    } else if (top) {
      int nxt = stk[top--];
      head[i] = update(head[nxt + 1], 1, n, nxt);
    }
  }
  long long res = 0;
  for (int i = 1; i <= n; i++) {
    int pos = SA.sa[i] + 1;
    int x = pos + SA.height[i];
    int y = n;
    res += (query(head[pos], 1, n, x, y));
  }
  printf("%lld\n", res);
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
template <typename T>
T In() {
  char ch;
  T n = 0;
  bool ng = false;
  while (1) {
    ch = getchar();
    if (ch == '-') {
      ng = true;
      ch = getchar();
      break;
    }
    if (ch >= '0' && ch <= '9') break;
  }
  while (1) {
    n = n * 10 + (ch - '0');
    ch = getchar();
    if (ch < '0' || ch > '9') break;
  }
  return (ng ? -n : n);
}
template <class T, class first>
inline bool checkbit(T a, first pos) {
  T t = 1;
  return ((a & (t << pos)) > 0);
}
template <class T, class first>
inline T setbit(T a, first pos) {
  T t = 1;
  return (a | (t << pos));
}
template <class T, class first>
inline T resetbit(T a, first pos) {
  T t = 1;
  return (a & (~(t << pos)));
}
template <class T, class first>
inline T togglebit(T a, first pos) {
  T t = 1;
  return (a ^ (t << pos));
}
template <typename T>
T POW(T base, T power) {
  T ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base);
    base = (base * base);
    power >>= 1;
  }
  return ret;
}
template <typename T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <typename T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / GCD(a, b));
}
template <typename T>
T EUCLIDE(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <typename T>
T ABS(T a) {
  if (a < 0)
    return -a;
  else
    return a;
}
long long Bigmod(long long base, long long power, long long _MOD) {
  long long ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base) % _MOD;
    base = (base * base) % _MOD;
    power >>= 1;
  }
  return ret;
}
long long ModInverse(long long number, long long _MOD) {
  return Bigmod(number, _MOD - 2LL, _MOD);
}
template <typename T>
double DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
long long isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
void BINARY(int n) {
  bitset<31> a = n;
  cout << a << endl;
}
void P_ARR(int *ar, int a, int b) {
  if (a > b) swap(a, b);
  if (a <= b) cout << ar[a];
  for (int i = a + 1; i <= b; i++) cout << " " << ar[i];
  cout << endl;
}
template <class T>
inline void make_unique_vec(vector<T> &vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
template <class T>
inline void make_unique_arr(T *ar, int &n) {
  sort(ar + 1, ar + n + 1);
  n = unique(ar + 1, ar + n + 1) - ar - 1;
}
const int N = 500007;
struct SUFFIX_ARRAY {
  int wa[N], wb[N], ws[N], wv[N], r[N];
  int len;
  int rnk[N];
  int height[N];
  int sa[N];
  int cmp(int *ar, int a, int b, int l) {
    return (ar[a] == ar[b]) && (ar[a + l] == ar[b + l]);
  }
  void DA(int n, int m) {
    int i, j, p, *x = wa, *y = wb, *t;
    for (i = 0; i < m; i++) ws[i] = 0;
    for (i = 0; i < n; i++) ws[x[i] = r[i]]++;
    for (i = 1; i < m; i++) ws[i] += ws[i - 1];
    for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i;
    for (j = 1, p = 1; p < n; j *= 2, m = p) {
      for (p = 0, i = n - j; i < n; i++) y[p++] = i;
      for (i = 0; i < n; i++)
        if (sa[i] >= j) y[p++] = sa[i] - j;
      for (i = 0; i < n; i++) wv[i] = x[y[i]];
      for (i = 0; i < m; i++) ws[i] = 0;
      for (i = 0; i < n; i++) ws[wv[i]]++;
      for (i = 1; i < m; i++) ws[i] += ws[i - 1];
      for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i];
      for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
        x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
    }
  }
  void calheight(int n) {
    int i, j, k = 0;
    for (i = 1; i <= n; i++) rnk[sa[i]] = i;
    for (i = 0; i < n; height[rnk[i++]] = k)
      for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++)
        ;
  }
  void generate(char *s) {
    for (len = 0; s[len]; len++) r[len] = (int)s[len];
    r[len] = 0;
    DA(len + 1, 128);
    calheight(len);
  }
  void print() {
    cout << "length :  " << len << endl;
    cout << "s[n] = '$' " << endl;
    cout << "sorted suffix index(0 based) : " << endl;
    for (int i = 0; i <= len; i++) cout << sa[i] << " , ";
    cout << endl;
    cout << "rank of suffix " << endl;
    for (int i = 0; i <= len; i++) cout << rnk[i] << " , ";
    cout << endl;
    cout << "LCP between i and i-1 " << endl;
    for (int i = 0; i <= len; i++) cout << height[i] << " , ";
    cout << endl;
  }
} SA;
char s[500007];
struct node {
  int sum;
  node *l, *r;
  node() {
    sum = 0;
    l = r = NULL;
  }
};
node tree[500007 * 21];
node *head[500007];
int avail;
node *update(node *pre, int s, int e, int pos) {
  node *ob = &tree[++avail];
  if (pre != NULL) *ob = *pre;
  if (s == e) {
    ob->sum++;
    return ob;
  }
  int mid = (s + e) >> 1;
  if (pos <= mid)
    ob->l = update(ob->l, s, mid, pos);
  else
    ob->r = update(ob->r, mid + 1, e, pos);
  ob->sum = 0;
  if (ob->l != NULL) ob->sum += ob->l->sum;
  if (ob->r != NULL) ob->sum += ob->r->sum;
  return ob;
}
int query(node *ob, int s, int e, int x, int y) {
  if (s > e) return 0;
  if (x > y) return 0;
  if (ob == NULL) return 0;
  if (s == x && e == y) {
    return ob->sum;
  }
  int mid = (s + e) >> 1;
  if (y <= mid)
    return query(ob->l, s, mid, x, y);
  else if (x > mid)
    return query(ob->r, mid + 1, e, x, y);
  else {
    int lt = query(ob->l, s, mid, x, mid);
    int rt = query(ob->r, mid + 1, e, mid + 1, y);
    return (lt + rt);
  }
}
int stk[500007];
int nxt[500007];
int top;
int main() {
  int n;
  scanf("%d", &(n));
  ;
  scanf("%s", s + 1);
  SA.generate(s + 1);
  head[0] = new node();
  head[n + 1] = new node();
  for (int i = n; i >= 1; i--) {
    head[i] = head[n + 1];
    if (s[i] == ')') {
      stk[++top] = i;
    } else if (top) {
      int nxt = stk[top--];
      head[i] = update(head[nxt + 1], 1, n, nxt);
    }
  }
  long long res = 0;
  for (int i = 1; i <= n; i++) {
    int pos = SA.sa[i] + 1;
    int x = pos + SA.height[i];
    int y = n;
    res += (query(head[pos], 1, n, x, y));
  }
  printf("%lld\n", res);
  return 0;
}

```