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




public class mymy
{

	static class node
	{
		char data;int indx;node link=null;
		node(char c,int j)
		{
			data=c;indx=j;
		}
	}

	static class stack
	{
		node front=null;

		void insert(node n)
		{
			if(front==null)
				front=n;
			else
			{
				if(front.data=='(' && n.data==')')
				{
					bal[n.indx]=0;bal[front.indx]=0;
					front=front.link;
				}
				else
				{
					n.link=front;
					front=n;
				}
			}
		}
	}
	static int[] bal;
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));	

		
	public static void main(String[] args)throws IOException{
		
			int n=Integer.parseInt(br.readLine());

			String s=br.readLine();

			bal=new int[n];
			Arrays.fill(bal,1);

			stack st=new stack();


			for(int i=0;i<n;i++)
			{
				st.insert(new node(s.charAt(i),i));
			}

			// System.out.println(Arrays.toString(bal));

			// ( left  			) right

			int[] left=new int[n],right=new int[n];

			for(int i=0;i<n;i++)
			{
				if(bal[i]==1)
				{
					if(s.charAt(i)=='(')
						left[i]=1;
					else
						right[i]=1;
				}
			}
			// System.out.println(Arrays.toString(left));
			// System.out.println(Arrays.toString(right));	
			int[] preLeft=new int[n],suffLeft=new int[n];
			int[] preRight=new int[n],suffRight=new int[n];
			for(int i=0;i<n;i++)
			{
				preRight[i]=right[i];preLeft[i]=left[i];
				suffRight[i]=right[i];suffLeft[i]=left[i];
			}
			for(int i=1;i<n;i++)
			{
				preLeft[i]+=preLeft[i-1];
				preRight[i]+=preRight[i-1];
			}
			for(int i=n-2;i>=0;i--)
			{
				suffLeft[i]+=suffLeft[i+1];
				suffRight[i]+=suffRight[i+1];
			}
			// System.out.println(Arrays.toString(preLeft));
			// System.out.println(Arrays.toString(suffLeft));	
			// System.out.println(Arrays.toString(preRight));
			// System.out.println(Arrays.toString(suffRight));	

			int ans=0;

			for(int i=0;i<n;i++)
			{
				int picheLeft=preLeft[i]-left[i];
				int aageLeft=suffLeft[i]-left[i];
				int picheRight=preRight[i]-right[i];
				int aageRight=suffRight[i]-right[i];
				// System.out.println(picheLeft+" "+picheRight+" "+aageLeft+" "+aageRight);
				if(bal[i]==0)
				{
					if(s.charAt(i)=='(')
					{
						if(picheLeft==2 && aageRight==0 && aageLeft==0 && picheRight==0)
							ans++;
					}
					else
					{
						if(picheLeft==0 && aageRight==2 && aageLeft==0 && picheRight==0)
							ans++;
					}
				}
				else
				{
					if(s.charAt(i)=='(')
					{
						if(picheLeft==1 && aageRight==0 && aageLeft==0 && picheRight==0)
							ans++;
					}
					else
					{
						if(picheLeft==0 && aageRight==1 && aageLeft==0 && picheRight==0)
							ans++;
					}
				}
			}
			System.out.println(ans);
			

	}
	
}