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.*;

public class F implements Runnable {
	public static void main (String[] args) {new Thread(null, new F(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");
		
		int n = fs.nextInt();
		char[] str = fs.next().toCharArray();
		int[] prefSum = new int[n+1];
		for(int i = n-1; i >= 0; i--) {
			prefSum[i] = prefSum[i+1];
			if(str[i] == ')') prefSum[i]--;
			else prefSum[i]++;
		}
		IntList[] locs = new IntList[2*n+1];
		int[] myLoc = new int[n+1];
		for(int i = 0; i < locs.length; i++) locs[i] = new IntList();
		for(int i = 0; i <= n; i++) {
			int idx = map(prefSum[i], n); 
			myLoc[i] = locs[idx].size(); 
			locs[idx].add(i);
		}

		RMQ rmq = new RMQ(prefSum);
		int[] totalCounts = new int[n];
		int[] bestPositions = new int[n];

		for(int i = 0; i < n; i++) {
			if(str[i] == ')') continue;
			int idx = map(prefSum[i], n);

			int lo = myLoc[i]+1, hi = locs[idx].size()-1;
			int bestPos = -1;
			for(int bs = 0; bs <= 50 && lo <= hi; bs++) {
				int mid = (lo+hi)/2;
				int pos = locs[idx].get(mid);
				int rMax = rmq.query(i, pos-1) - prefSum[i];
				if(rMax > 0) hi = mid-1;
				else {
					bestPos = mid; lo = mid+1;
				}
			}
			bestPositions[i] = bestPos;
			if(bestPos == -1) continue;
			totalCounts[i] = bestPos-myLoc[i];
		}

		int[] sa = suffixArray(str);
		int[] rsa = new int[n];
		for(int i = 0; i < n; i++) rsa[sa[i]] = i;
		int[] lcp = lcp(sa, str);
		
		long res = totalCounts[sa[0]]; 
		for(int i = 1; i < n; i++) {
			int idx = sa[i], idx2 = map(prefSum[idx], n);
			if(str[idx] == ')') break;
			if(totalCounts[idx] == 0) continue;
			
			int val = lcp[i-1];
			int lo = myLoc[idx]+1, hi = bestPositions[idx];
			int cut = -1;
			for(int bs = 0; bs < 50 && lo <= hi; bs++) {
				int mid = (lo+hi)/2;
				int pos = locs[idx2].get(mid);
				if(pos-idx > val) {
					hi = mid-1;
				}
				else {
					cut = mid;
					lo = mid+1;
				}
			}
			if(cut == -1) res += totalCounts[idx];
			else res += totalCounts[idx] - (cut-myLoc[idx]);
		}
		
		out.println(res);
		out.close();
	}

	int map(int v, int n) {
		return v+n;
	}

	public int[] suffixArray(char[] S) {
		int n = S.length;
		Integer[] order = new Integer[n];
		for (int i = 0; i < n; i++)
			order[i] = n - 1 - i;

		Arrays.sort(order, (a, b) -> Character.compare(S[a], S[b]));

		int[] sa = new int[n];
		int[] classes = new int[n];
		for (int i = 0; i < n; i++) {
			sa[i] = order[i];
			classes[i] = S[i];
		}

		for (int len = 1; len < n; len *= 2) {
			int[] c = classes.clone();
			for (int i = 0; i < n; i++) {
				classes[sa[i]] = i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < n && c[sa[i - 1] + len / 2] == c[sa[i] + len / 2] ? classes[sa[i - 1]] : i;
			}
			int[] cnt = new int[n];
			for (int i = 0; i < n; i++)
				cnt[i] = i;
			int[] s = sa.clone();
			for (int i = 0; i < n; i++) {
				int s1 = s[i] - len;
				if (s1 >= 0)
					sa[cnt[classes[s1]]++] = s1;
			}
		}
		return sa;
	}

	public int[] lcp(int[] sa, char[] s) {
		int n = sa.length;
		int[] rank = new int[n];
		for (int i = 0; i < n; i++)
			rank[sa[i]] = i;
		int[] lcp = new int[n - 1];
		for (int i = 0, h = 0; i < n; i++) {
			if (rank[i] < n - 1) {
				for (int j = sa[rank[i] + 1]; Math.max(i, j) + h < s.length && s[i + h] == s[j + h]; ++h)
					;
				lcp[rank[i]] = h;
				if (h > 0)
					--h;
			}
		}
		return lcp;
	}

	class RMQ {
		int[] vs;
		int[][] lift;

		public RMQ(int[] vs) {
			this.vs = vs;
			int n = vs.length;
			int maxlog = Integer.numberOfTrailingZeros(Integer.highestOneBit(n)) + 2;
			lift = new int[maxlog][n];
			for (int i = 0; i < n; i++)
				lift[0][i] = vs[i];
			int lastRange = 1;
			for (int lg = 1; lg < maxlog; lg++) {
				for (int i = 0; i < n; i++) {
					lift[lg][i] = Math.max(lift[lg - 1][i], lift[lg - 1][Math.min(i + lastRange, n - 1)]);
				}
				lastRange *= 2;
			}
		}

		public int query(int low, int hi) {
			int range = hi - low + 1;
			int exp = Integer.highestOneBit(range);
			int lg = Integer.numberOfTrailingZeros(exp);
			return Math.max(lift[lg][low], lift[lg][hi - exp + 1]);
		}
	}

	int[] EMPTY = {};
	class IntList {
		int n = 0, a[] = EMPTY;
		void add(int v) {
			if (n >= a.length)
				a = Arrays.copyOf(a, (n << 2) + 8);
			a[n++] = v;
		}
		int get(int idx) { return a[idx]; }
		int size() { return n; }
		public String toString() {
			return Arrays.toString(Arrays.copyOfRange(a, 0, n));
		}
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}

	}

}