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

public class AlmostRegularBracketSequence {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n = in.nextInt();
		String s = in.next();
		int r = solve(n, s);
		System.out.println(r);
		in.close();
	}

	private static int solve(int n, String str) {
		Stack<Integer> s = new Stack<>();
		char[] chars = str.toCharArray();
		int pos = Integer.MIN_VALUE;
		for (int i = 0; i < chars.length; i++) {
			if (chars[i] == '(') {
				s.push(i + 1);
			} else {
				if (!s.isEmpty() && s.peek() > 0) {
					s.pop();
				} else {
					s.push(-i - 1);
				}
			}
		}
		if (s.size() == 2) {
			int r = s.pop();
			int l = s.pop();
			if (l < 0 && r < 0) {
				int cnt = 0;
				for (int i = -l - 1; i >= 0; i--) {
					if (chars[i] == ')') {
						cnt++;
					}
				}
				return cnt;
			}
			if (l > 0 && r > 0) {
				int cnt = 0;
				for (int i = r - 1; i < chars.length; i++) {
					if (chars[i] == '(') {
						cnt++;
					}
				}
				return cnt;
			}
			return 0;
		}
		return 0;
	}

	static String getStr(long[] a) {
		String[] str = new String[a.length];
		for (int i = 0; i < a.length; i++) {
			str[i] = a[i] + "";
		}
		return String.join(" ", str);
	}
}
