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

public class Main {
	
	private static boolean[] flag = new boolean[1000010];
	private static int[] cnt = new int[1000010];
	
	public static void main(String[] args) {			
	
		Scanner scan = new Scanner(System.in);

		int i , j , n = scan.nextInt();
		String string = scan.next();
		
		boolean isLegal = true;
		int count = 0 , ans = 0;
		for (i = n - 1;i >= 0;i --) {
			if (string.charAt(i) == ')') {
				count ++;
			} else {
				if (count > 0) {
					count --;
				} else {
					isLegal = false;
					count --;
				}
			}			
			if (isLegal) {
				flag[i] = true;
			} else {
				flag[i] = false;
			}
			cnt[i] = count;
		}
		flag[n] = true;
		
		count = 0;
		isLegal = true;
		for (i = 0;i < n;i ++) {
			// change current
			if (string.charAt(i) == '(') {
				if (isLegal && count > 0 && (count - 1) == cnt[i + 1] && flag[i + 1]) {
					ans ++;
				}
			} else {
				if (isLegal && count + 1 == cnt[i + 1] && flag[i + 1]) {
					ans ++;
				}
			}
			
			if (string.charAt(i) == '(') {
				count ++;
			} else {
				if (count > 0) {
					count --;
				} else {
					isLegal = false;
					count --;
				}
			}
		}
		
		System.out.println(ans);

	}
	

    
}






