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 = 0 , close = 0 ; 
		
		int [] cnt1 = new int [n] ; 
		int [] cnt2 = new int [n] ; 
		
		for(int i =  0 ; i < n ;i++)
		{
			if(s[i] == '(')
				open ++ ;
			else
				open -- ; 
			
			if(s[n - i - 1] == '(')
				close --;
			else
				close ++ ; 
			
			left &= open >= 0 ; right &= close >= 0 ; 
			cnt1[i] = open ; 
			cnt2[i] = close ; 
		}
		
		if(!left && !right) {System.out.println(0);return;}
		
		int ans  = 0 ;
		int [] cnt = left ? cnt1 : cnt2 ; 
		char [] tmp = s.clone() ; 
		
		if(right)
			for(int i = 0 ; i < n ;i++)
				s[n - i - 1] = tmp[i] == ')' ? '(' : ')' ; 
			
		
		SparseTable sp = new SparseTable(cnt) ; 
		for(int i = 0 ; i < n ;i++)
		{
			int diff = s[i] == '(' ? cnt[n - 1] - 2 : cnt[n - 1] + 2 ; 
			
			if(sp.query(i, n - 1) - 2 < 0) continue ;
 			
 			if(diff == 0) ans ++ ; 
 			
		}
		
		
		
		out.println(ans);
		
		out.flush();
		out.close();
		
	}
	static  class SparseTable {                                          
		  
		int A[], SpT[][];
		
		SparseTable(int[] A) 
		{
			int n = A.length;	this.A = A;
			int k = (int)Math.floor(Math.log(n) / Math.log(2)) + 1;
			SpT = new int[n][k];
			
			for (int i = 0; i < n; i++) 
				SpT[i][0] = i; 					// RMQ of sub array starting at index i and of length 2^0=1
		
			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];    		// start at index i of length 2^(j-1)
					else                  					// start at index i+2^(j-1) of length 2^(j-1)
						SpT[i][j] = SpT[i+(1<<(j-1))][j-1];
		 }

		  int query(int i, int j) 
		  {
			  
		    int k = (int)Math.floor(Math.log(j-i+1) / Math.log(2)); // 2^k <= (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 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;
		}
	}

}