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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * 653F
 * O(n*log(n)) time,
 * θ(n) space
 *
 * @author artyom
 */
public class _653F implements Runnable {
    private BufferedReader in;
    private int[] hs;
    private List<Integer>[] ps;
    private long ans;
    private int base;

    private void solve() throws IOException {
        int n = nextInt();
        CharSequence s = nextToken();
        hs = new int[n + 1];
        int max = base = 0;
        for (int i = 1; i <= n; i++) {
            hs[i] = s.charAt(i - 1) == '(' ? hs[i - 1] + 1 : hs[i - 1] - 1;
            max = Math.max(max, hs[i]);
            base = Math.min(base, hs[i]);
        }
        ps = new List[max - base + 1];
        for (int i = 0; i <= n; i++) {
            int ix = hs[i] - base;
            if (ps[ix] == null) {
                ps[ix] = new ArrayList<>();
            }
            ps[ix].add(i - 1);
        }
        ans = 0;
        SuffixTreeNode root = buildSuffixTree(s);
        for (SuffixTreeNode child : root.children) {
            if (child != null) {
                calc(child);
            }
        }
    }

    private void calc(SuffixTreeNode node) {
        int offset = hs[node.start - node.depth] - base;
        int to = node.end - 1;
        int negIndex = offset > 0 ? findLeftmostBetween(ps[offset - 1], node.start, to) : -1;
        if (negIndex >= 0) {
            to = negIndex - 1;
        }
        ans += count(ps[offset], node.start, to);
        if (negIndex < 0 && node.children != null) {
            for (SuffixTreeNode child : node.children) {
                calc(child);
            }
        }
    }

    private static int findLeftmostBetween(List<Integer> ls, int from, int to) {
        int il = binarySearch(ls, from), ir = binarySearch(ls, to);
        if (il < 0) {
            il = -il - 1;
        }
        if (ir < 0) {
            ir = -ir - 2;
        }
        return ir < il ? -1 : ls.get(il);
    }

    private static int binarySearch(List<Integer> ls, int value) {
        int l = 0, r = ls.size() - 1;
        while (l <= r) {
            int m = (l + r) >> 1;
            if (ls.get(m) == value) {
                return m;
            }
            if (ls.get(m) < value) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -(l + 1);
    }

    private static int count(List<Integer> ls, int from, int to) {
        int il = binarySearch(ls, from), ir = binarySearch(ls, to);
        if (il < 0) {
            il = -il - 1;
        }
        if (ir < 0) {
            ir = -ir - 2;
        }
        return ir - il + 1;
    }

    //--------------------------------------------------------------
    public static void main(String[] args) {
        new _653F().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            solve();
            System.out.print(ans);
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private String nextToken() throws IOException {
        return in.readLine();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private static SuffixTreeNode buildSuffixTree(CharSequence s) {
        int n = s.length();
        byte[] a = new byte[n];
        for (int i = 0; i < n; i++) {
            a[i] = (byte) (s.charAt(i) - '(');
        }
        SuffixTreeNode root = new SuffixTreeNode(0, 0, 0, null);
        SuffixTreeNode node = root;
        for (int i = 0, tail = 0; i < n; i++, tail++) {
            SuffixTreeNode last = null;
            while (tail >= 0) {
                SuffixTreeNode ch = node.children[a[i - tail]];
                while (ch != null && tail >= ch.length()) {
                    tail -= ch.length();
                    node = ch;
                    ch = ch.children[a[i - tail]];
                }
                if (ch == null) {
                    node.children[a[i]] = new SuffixTreeNode(i, n, node.depth + node.length(), i);
                    if (last != null) {
                        last.suffixLink = node;
                    }
                    last = null;
                } else {
                    byte t = a[ch.start + tail];
                    if (t == a[i]) {
                        if (last != null) {
                            last.suffixLink = node;
                        }
                        break;
                    } else {
                        SuffixTreeNode splitNode = new SuffixTreeNode(ch.start, ch.start + tail, node.depth + node.length(), null);
                        splitNode.children[a[i]] = new SuffixTreeNode(i, n, ch.depth + tail, i);
                        splitNode.children[t] = ch;
                        ch.start += tail;
                        ch.depth += tail;
                        node.children[a[i - tail]] = splitNode;
                        if (last != null) {
                            last.suffixLink = splitNode;
                        }
                        last = splitNode;
                    }
                }
                if (node == root) {
                    tail--;
                } else {
                    node = node.suffixLink;
                }
            }
        }
        return root;
    }

    private static final class SuffixTreeNode {
        int depth; // The number of characters from root to this node
        int start; // Inclusive
        int end; // Exclusive
        final SuffixTreeNode[] children;
        SuffixTreeNode suffixLink;

        private SuffixTreeNode(int start, int end, int depth, Integer position) {
            this.depth = depth;
            this.start = start;
            this.end = end;
            // Save some space and time
            children = position == null ? new SuffixTreeNode[2] : null;
        }

        /**
         * @return the number of characters on the edge to the parent.
         */
        final int length() {
            return end - start;
        }

        @Override
        public String toString() {
            return "(" + start + ',' + (end - 1) + ')';
        }
    }
}