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
//codeforces_1095E

import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import static java.lang.Math.*;
import java.math.*;

public class Main{

	static PrintWriter go = new PrintWriter(System.out);
	static long mod = 998244353;

	public static void main(String args[]) throws IOException,FileNotFoundException {
		BufferedReader gi = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(gi.readLine());
		char[] l = gi.readLine().toCharArray();
		if ( l[0] == ')' && l[n-1] == '(' ){
			go.println(0);
			go.close();
			return;
		}
		int acc = 0,p=0;
		int ans = 0;
		boolean flag = false;
		for ( int k = 0; k < n; k++){
			acc += (l[k]=='('?1:-1);
			p += (l[k]==')'?1:0);
			if ( acc == -1 && !flag ){ ans = p; flag = true; }
			if ( acc < -2 ){
				go.println(0);
				go.close();
				return;
			}
		}
		if ( acc == -2 ){
			go.println(ans);
			go.close();
			return;
		}
		acc = p = ans = 0;
		flag = false;
		for ( int k = n-1; k >= 0; k--){
			acc += (l[k]==')'?1:-1);
			p += (l[k]=='('?1:0);
			if ( acc == -1 && !flag ){ ans = p; flag = true; }
			if ( acc < -2 ){
				go.println(0);
				go.close();
				return;
			}
		}if ( acc != -2 ){ ans = 0; }
		go.println(ans);
		go.close();
	}

	static int[] parseArray(BufferedReader gi) throws IOException{
		String[] line = gi.readLine().trim().split(" ");
		int[] rez = new int[line.length];
		for ( int k = 0; k < line.length; k++){
			rez[k] = Integer.parseInt(line[k]);
		}
		return rez;
	}

}
