You are given a bracket sequence s consisting of n opening '(' and closing ')' brackets.

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

You can change the type of some bracket s_i. It means that if s_i =  ')' then you can change it to '(' and vice versa.

Your task is to calculate the number of positions i such that if you change the type of the i-th bracket, then the resulting bracket sequence becomes regular.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 10^6) — the length of the bracket sequence.

The second line of the input contains the string s consisting of n opening '(' and closing ')' brackets.

Output

Print one integer — the number of positions i such that if you change the type of the i-th bracket, then the resulting bracket sequence becomes regular.

Examples

Input


6
(((())


Output


3


Input


6
()()()


Output


0


Input


1
)


Output


0


Input


8
)))(((((


Output


0
import java.io.*;
import java.util.*;

public class E {

	static StringBuilder st = new StringBuilder();

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();
		char[] s = sc.next().toCharArray();

		boolean left = true, right = true;

		int[] open = new int[n] , close = new int [n];
		
		for (int i = 0; i < n; i++) 
		{
			open[i] += (i > 0 ? open[i - 1 ] : 0) + (s[i] == '(' ? 1 : -1) ; 
			close[i] += (i > 0 ? close[i - 1] : 0) + (s[n - i - 1] == '(' ? -1 : 1) ; 
			left &= open[i] >= 0; right &= close[i] >= 0;
		}
		
		int ans = 0;
		int[] cnt = left ? open : close;
		s = right ? reverse(s) : s ; 
		
		SparseTable sp = new SparseTable(cnt);
		
		for (int i = 0; i < n; i++) 
			if (sp.query(i, n - 1) >= 2&& (s[i] == '(' ? cnt[n - 1] - 2 : cnt[n - 1] + 2) == 0)
					ans++;
		
		out.println(!left && !right ? 0 : ans);

		out.flush();
		out.close();

	}
	static char [] reverse(char [] a )
	{
		int n = a.length ;char temp [] = a.clone() ; 
		
		for(int i = 0 ; i < n ;i++)
			a[n - i - 1] =  temp[i] == ')' ? '(' : ')' ; 
		
		return a ;
	}
	static class SparseTable {

		int A[], SpT[][];

		SparseTable(int[] A) {
			computeLog();
			int n = A.length;
			this.A = A;
			int k = log2[n] + 1;
			SpT = new int[n][k];
			for (int i = 0; i < n; i++)
				SpT[i][0] = i; 

			for (int j = 1; (1 << j) <= n; j++)
				for (int i = 0; i + (1 << j) - 1 < n; i++)
					if (A[SpT[i][j - 1]] <= A[SpT[i + (1 << (j - 1))][j - 1]])
						SpT[i][j] = SpT[i][j - 1]; 
					else 
						SpT[i][j] = SpT[i + (1 << (j - 1))][j - 1];
		}

		int query(int i, int j) {

			int k = log2[j - i + 1] ;

			if (A[SpT[i][k]] <= A[SpT[j - (1 << k) + 1][k]])
				return A[SpT[i][k]];
			else
				return A[SpT[j - (1 << k) + 1][k]];

		}

		static int[] log2;

		static void computeLog() {
			log2 = new int[1000001];
			log2[1] = 0;
			for (int i = 1; i <= 20; ++i)
				for (int j = 1 << i; j <= 1 << (i + 1) && j <= 1e6; ++j)
					log2[j] = i;

		}
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() throws Exception {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());

			return st.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(next());
		}

		long nextLong() throws Exception {
			return Long.parseLong(next());
		}

		double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}

	}

	static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

}