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

public class CF1095E {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		char[] cc = br.readLine().toCharArray();
		int[] pp = new int[n + 1];
		int[] bb = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			pp[i] = pp[i - 1] + (cc[i - 1] == '(' ? 1 : -1);
			bb[i] = Math.min(bb[i - 1], pp[i]);
		}
		int[] qq = new int[n + 2];
		int[] dd = new int[n + 2];
		for (int i = n; i >= 1; i--) {
			qq[i] = qq[i + 1] + (cc[i - 1] == ')' ? 1 : -1);
			dd[i] = Math.min(dd[i + 1], qq[i]);
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++)
			if (bb[i - 1] == 0 && dd[i + 1] == 0) {
				int c = cc[i - 1] == '(' ? -1 : 1;
				if (pp[i - 1] + c == qq[i + 1])
					cnt++;
			}
		System.out.println(cnt);
	}
}
