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.util.Arrays;
import java.util.Scanner;


public class CF529E {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if(n%2==1){
			System.out.println(0);
			return;
		}
		char[] c = sc.next().toCharArray();
		int[] vals = new int[n];
		for(int i=0; i<n; i++) vals[i] = c[i]=='(' ? 1 : -1;
		int[] l = new int[n];
		int[] r = new int[n];
		boolean[] lCan = new boolean[n];
		boolean[] rCan = new boolean[n];
		l[0] = vals[0];
		r[n-1] = -vals[n-1];
		lCan[0] = vals[0]==1;
		rCan[n-1] = vals[n-1]==-1;
		for(int i=1; i<n; i++) {
			l[i] = l[i-1]+vals[i];
			lCan[i] = lCan[i-1] && l[i]>=0;
		}
		for(int i=n-2; i>=0; i--) {
			r[i] = r[i+1]-vals[i];
			rCan[i] = rCan[i+1] && r[i]>=0;
		}
		int total = 0;
//		System.out.println(Arrays.toString(l)+"\n"+Arrays.toString(r));
//		System.out.println(Arrays.toString(lCan)+"\n"+Arrays.toString(rCan));
		for(int i=0; i<n; i++)
			if((i==0 || lCan[i-1]) && (i==n-1 || rCan[i+1])){
				int left = i==0 ? 0 : l[i-1];
				int right = i==n-1 ? 0 : r[i+1];
//				System.out.println(i+" "+left+" "+right);
				if((c[i]=='(' && left>=0 && left-1-right==0) || (c[i]==')' && left+1-right==0)) total++;
			}
		System.out.println(total);
	}
}
