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.*;
import java.io.*;

public class Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		out.println(work());
		out.flush();
	}
	long mod=1000000007;
	long gcd(long a,long b) {
		return b==0?a:gcd(b,a%b);
	}
	int work() {
		int n=in.nextInt();
		if(n%2==1)return 0;
		String s=in.next();
		int cnt=0;
		for(int i=0;i<n;i++) {
			if(s.charAt(i)=='(') {
				cnt++;
			}else {
				cnt--;
			}
		}
		if(cnt==2) {
			int c=0;
			int index=-1;
			int ret=0;
			for(int i=n-1;i>=0;i--) {
				if(s.charAt(i)=='(') {
					c++;
				}else {
					c--;
				}
				if(c>0) {
					index=i;
					ret=(n-1-i)/2+1;
					break;
				}
			}
			c=0;
			for(int i=0;i<n;i++) {
				if(i==index||s.charAt(i)==')') {
					c--;
				}else {
					c++;
				}
				if(c<0)return 0;
			}
			return ret;
		}
		if(cnt==-2) {
			int c=0;
			int index=-1;
			int ret=0;
			for(int i=0;i<n;i++) {
				if(s.charAt(i)=='(') {
					c++;
				}else {
					c--;
				}
				if(c<0) {
					index=i;
					ret=i/2+1;
					break;
				}
			}
			c=0;
			for(int i=n-1;i>=0;i--) {
				if(i==index||s.charAt(i)=='(') {
					c++;
				}else {
					c--;
				}
				if(c>0)return 0;
			}
			return ret;
		}
		return 0;
	}
}



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	public String next() 
	{
		if(st==null || !st.hasMoreElements())
		{
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	public int nextInt() 
	{
		return Integer.parseInt(next());
	}

	public long nextLong()
	{
		return Long.parseLong(next());
	}
}