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.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {

		//(()()((())(()()()())))()))
		
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		
		int n = in.nextInt();
		in.nextLine();
		char[] line = in.nextLine().toCharArray();
		
		int[] diff = new int[n];
		boolean[] valido = new boolean[n];
		diff[0] = line[0] == '(' ? 1 : -1;
		valido[0] = diff[0] == 1;
		
		boolean ok = diff[0] == 1;
		boolean impossible = false;
		
		for(int i = 1; i < n; i++) {
			
			diff[i] = line[i] == '(' ? diff[i - 1] + 1 : diff[i - 1] - 1; 
			valido[i] = valido[i - 1] && diff[i] >= 0;
			
			if(diff[i] < 0) ok = false;
			if(diff[i] < -2) impossible = true;
		}
		
		ok = ok && diff[n - 1] == 0;
		
		if(ok || impossible) {
			System.out.println(0);
			return;
		}
		
		int tot = 0;
		
		for(int i = 0; i < n; i++) {
			
			if(line[i] == ')' && diff[n - 1] + 2 == 0) {
				tot++;
			}
			
			if(diff[i] < 0) break;
		}
		
		for(int i = n - 1; i >= 0; i--) {
			
			if(diff[i] < 2) break;
			
			if(valido[i] && line[i] == '(' && diff[n - 1] - 2 == 0) {
				tot++;
			}
		}
		
		System.out.println(tot);
	}
}