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


/*
6
(())))

*/

public class A {
	static FastReader sc=null;
	
	public static void main(String[] args) {
		sc=new FastReader();
		int n=sc.nextInt();
		char line[]=sc.next().toCharArray();
		
		if(n%2==1) {
			System.out.println(0);
			return;
		}
		
		int curr=0,ans=0;
		for(int i=0;i<n;i++) {
			if(line[i]=='(')curr++;
			else {
				if(curr>0)curr--;
				else {
					ans++;
					curr++;
				}
			}
		}
		ans+=curr/2;
		if(ans!=1)System.out.println(0);
		
		else{
			int pos=go(line);
			reverse(line);
			pos+=go(line);
			System.out.println(pos);
		}
		
	
	}
	static void reverse(char line[]) {
		char temp[]=line.clone();
		for(int i=0;i<line.length;i++) {
			line[i]=temp[line.length-i-1]==')'?'(':')';
		}
	}
	static int go(char line[]) {
		int n=line.length;
		int pos=0,curr=0;
		int ids[]=new int[n],preMin[]=new int[n],suffMin[]=new int[n];
		for(int i=0;i<n;i++) {
			if(line[i]=='(') curr++;
			else curr--;
			
			ids[i]=curr;
		}
		for(int i=n-1;i>=0;i--) {
			if(i==n-1)suffMin[i]=ids[i];
			else suffMin[i]=Math.min(suffMin[i+1], ids[i]);
		}
		
		for(int i=0;i<n;i++) {
			if(i==0)preMin[i]=ids[i];
			else preMin[i]=Math.min(preMin[i-1], ids[i]);
		}
		for(int i=1;i<n;i++) {
			if(line[i]=='(') {
				if(suffMin[i]>=2 && preMin[i]>=0)pos++;
			}
		}
		return pos;
	}
	
	
	static int[] ruffleSort(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i:a)al.add(i);
		Collections.sort(al);
		for(int i=0;i<a.length;i++)a[i]=al.get(i);
		return a;
	}
	static void print(int a[]) {
		for(int e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	
	static class FastReader{
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		String next() {
			while(!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				}
				catch(IOException e){
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int[] readArray(int n) {
			int a[]=new int[n];
			for(int i=0;i<n;i++)a[i]=sc.nextInt();
			return a;
		}
	}
}






