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 "(())()".

import java.io.*;
import java.util.*;
import java.math.*;

public class SuffixArray_NlogN_AC {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  static StringTokenizer st = new StringTokenizer("");

  public static String next() {
    try {
    while (!st.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null)
        return null;
      st = new StringTokenizer(s);
    }
    return st.nextToken();
    } catch(Exception e)  {
      return  null;
    }
  }

  public static void main(String[] asda) throws Exception {
    next();
    String s = next();
    int N = s.length();
    boolean[] open = new boolean[N];
    for (int k = 0; k < N; k++)
      open[k] = s.charAt(k) == '(';

    //
    couple = new int[N];
    Arrays.fill(couple, -1);
    Stack<Integer> stack = new Stack<>();
    for (int k = 0; k < N; k++) {
      if (open[k]) {
        stack.push(k);
      } else if (!stack.isEmpty())  {
        couple[ stack.pop() ] = k;
      }
    }

    // isHead[k] = true if k is a list head
    boolean[] isHead = new boolean[N];
    int listCount = 0;
    for (int k = N - 1; k >= 0; k--) if (couple[k] != -1) {
      int next = couple[k] + 1;
      if (next < N && isHead[next]) {
        isHead[next] = false;
        listCount--;
      }
      isHead[k] = true;
      listCount++;
    }

    //
    inList = new int[N];
    listPos = new int[N];
    lists = new int[listCount][];

    Arrays.fill(inList, -1);
    listCount = 0;
    for (int k = 0; k < N; k++) if (isHead[k]) {
      List<Integer> currentList = new ArrayList<>();
      int index = k;
      while (index < N && couple[index] != -1) {
        inList[index] = listCount;
        listPos[index] = currentList.size();
        currentList.add(index);
        if (couple[index] == -1)
          break;

        index = couple[index] + 1;
      }

      int[] array = new int[currentList.size()];
      for (int p = 0; p < array.length; p++)
        array[p] = currentList.get(p);

      lists[listCount++] = array;
    }

    // count them all
    SuffixArray suffixArray = new SuffixArray(s);
    long ans = 0;
    for (int index = 0; index < N; index++) {
      int suffix = suffixArray.pos[index];
      int lcp = suffixArray.LCP[index];
      ans += query(suffix, N) - query(suffix, suffix + lcp);
    }
    out.println(ans);
    //
    out.flush();
    System.exit(0);
  }

  // couple[k] is the index of the couple for k-th value, -1 is there is no couple
  static int[] couple;

  // inList[k] = in which list is stored the k-th value?, -1 if not in any
  static int[] inList;

  // lists[ inList[k] ][ listPos[k] ] = k
  static int[] listPos;
  static int[][] lists;

  // how many good intervals [begin, k] for begin <= k < end
  static int query(int begin, int end)  {
    //int end = inList.length;
    if (begin >= end) {
      return 0;
    }
    int listIndex = inList[begin];
    if (listIndex == -1) {
      return 0;
    }
    if (couple[begin] == -1 || couple[begin] >= end) {
      return 0;
    }

    int[] list = lists[listIndex];
    int lo = listPos[begin];
    int hi = list.length - 1;
    int rightmost = lo;
    while (lo <= hi)  {
      int mid = (lo + hi) >> 1;
      if (list[mid] < end) {
        rightmost = mid;
        lo = mid + 1;
      } else  {
        hi = mid - 1;
      }
    }

    if (couple[ list[rightmost] ] >= end) {
      rightmost--;
    }

    int left = listPos[begin];
    return left <= rightmost ? rightmost - left + 1 : 0;
  }
}


class SuffixArray {
  final String str; // input
  int N;
  Integer [] pos; // output
  int [] rank;  // output
  int LCP [];   // LCP[i] = Longest common prefix of suffix pos[i] and suffix pos[i - 1]

  public SuffixArray(final String str) {
    this.str = str;
    N = str.length();

    pos = new Integer[N];
    rank = new int[N];
    int [] cnt = new int[N];
    int [] next = new int[N];
    boolean [] bh = new boolean[N];
    boolean [] b2h = new boolean[N];

    // sort suffixes according to their first characters
    for (int i = 0; i < N; i++)
      pos[i] = i;

    Arrays.sort(pos, new Comparator<Integer>() {
      public int compare(Integer a, Integer b) {
        return str.charAt(a) - str.charAt(b);
      }
    });
    // {pos contains the list of suffixes sorted by their first
    // character}

    bh[0] = true;
    for (int i = 1; i < N; ++i) {
      bh[i] = str.charAt(pos[i]) != str.charAt(pos[i - 1]);
    }

    for (int h = 1; h < N; h <<= 1) {
      // {bh[i] == false if the first h characters of pos[i-1] == the
      // first h characters of pos[i]}
      int buckets = 0;
      for (int i = 0, j; i < N; i = j) {
        j = i + 1;
        while (j < N && !bh[j])
          j++;
        next[i] = j;
        buckets++;
      }
      if (buckets == N)
        break;

      for (int i = 0; i < N; i = next[i]) {
        cnt[i] = 0;
        for (int j = i; j < next[i]; ++j) {
          rank[pos[j]] = i;
        }
      }

      cnt[rank[N - h]]++;
      b2h[rank[N - h]] = true;
      for (int i = 0; i < N; i = next[i]) {
        for (int j = i; j < next[i]; ++j) {
          int s = pos[j] - h;
          if (s >= 0) {
            int head = rank[s];
            rank[s] = head + cnt[head]++;
            b2h[rank[s]] = true;
          }
        }
        for (int j = i; j < next[i]; ++j) {
          int s = pos[j] - h;
          if (s >= 0 && b2h[rank[s]]) {
            for (int k = rank[s] + 1; k < N && !bh[k] && b2h[k]; k++)
              b2h[k] = false;
          }
        }
      }
      for (int i = 0; i < N; ++i) {
        pos[rank[i]] = i;
        bh[i] |= b2h[i];
      }
    }
    

    // compute inverse of suffix array
    for (int i = 0; i < N; ++i)
      rank[ pos[i] ] = i;

    LCP = new int [N];
    LCP[0] = 0;
    for (int i = 0, h = 0; i < N; ++i)  {
      if ( rank[i] > 0 )  {
        int j = pos[ rank[i] - 1 ];
        while ( i + h < N && j + h < N && str.charAt(i+h) == str.charAt(j+h) )
          h++;
        LCP[ rank[i] ] = h;
        if ( h > 0 )
          h--;
      }
    }
  }
}
