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

public class E {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter pw = new PrintWriter(System.out);
		int n=sc.nextInt();
		char[]c=sc.nextLine().toCharArray();
		int[]pre=new int[n];
		int[]a=new int[n];
		int ans=0;
		for(int i=0;i<n;i++)
		{
			if(i>0)
				pre[i]=pre[i-1];
			if(c[i]=='(')
			{
				ans++;
				pre[i]++;
				a[i]++;;
			}
			else
			{	
				ans--;
				pre[i]--;
				a[i]--;
			}
		}
		int out=0;
//		System.out.println(Arrays.toString(pre));
		if(pre[n-1]!=-2 && pre[n-1]!=2)
		{
			System.out.println(0);
			return;
		}
		if(pre[n-1]==2)//means that there is "(" has to be closed
		{
			for(int i=n-1;i>=0;i--)
			{
				// ))(( -1,-2,1,2
				if(pre[i]<0)
				{
					System.out.println(0);
					return;
				}
			}
			for(int i=n-1;i>=0;i--)
			{
				// (())()((
				// (((()) == 2
				if(pre[i]<2) break;
				if(c[i]=='(')
					out++;
			}		
		}
		else// pre == -2 searching for extra ")" 
		{
			for(int i=0;i<n;i++)
				if(pre[i]<-2)
				{
					System.out.println(0);
					return;
				}
			int k=0;
			for(int i=0;i<n;i++)
			{
				//(())
				if(pre[i]<0)
				{
					k=i;
					break;
				}
			}
			for(int i=0;i<=k;i++)
			{
				if(c[i]==')')
					out++;
			}		
		}
		pw.print(out);
		pw.close();
	}
	static class SegmentTree
	{
		int[]sgt;
		int[]a;
		int[]lazy;
		int n;
		public SegmentTree(int[]a)
		{
			int log=(int)(Math.ceil(Math.log(a.length)/Math.log(2)));
			n=1<<log;
			sgt=new int[n<<1];//index 0 is unused
			lazy=new int[n<<1];
			this.a=a;
//			for(int i=0;i<a.length;i++)
//				sgt[a.length+i]=a[i];
//			builditer();
			buildrec(1,n,1);
		}
		public void builditer()
		{
			for(int i=a.length-1;i>0;i--)
				sgt[i]=sgt[i*2]+sgt[i*2+1];
		}
		public void buildrec(int l,int r,int n)
		{
			if(l==r)
			{	
				if(l-1<a.length)//l-1 because our array is zero indexed
					sgt[n]=a[l-1];
				return;
			}
			int mid=(r+l)/2;
			buildrec(l,mid,2*n);
			buildrec(mid+1,r,2*n+1);
			sgt[n]=sgt[2*n]+sgt[2*n+1];
		}
		public int query(int l,int r)//take zero index parameters
		{
			if(r==-1 || l==a.length)
				return 0;
			return query(1,n,1,l+1,r+1);
		}
		public int query(int s,int e,int i,int l,int r)
		{
			if(l<=s && r>=e)
				return sgt[i];
			if(r<s || l>e)
				return 0;
			int mid=e+s>>1;
			if(lazy[i]!=0)
				propagate(i,(e-s+1)/2);
			int left=query(s,mid,i*2,l,r);
			int right=query(mid+1,e,i*2+1,l,r);
			return left+right;
		}
		public void increment_rec(int l,int r,int idx,int i,int val)
		{
			if(l==r)
			{
				sgt[i]+=val;
				return;
			}
			int mid=l+r>>1;
			propagate(i,(r-l+1)/2);
			if(idx<=mid)
				increment_rec(l,mid,idx,i<<1,val);
			else
				increment_rec(mid+1,r,idx,i<<1|1 ,val);
			sgt[i]=sgt[i<<1]+sgt[i<<1|1];
		}
		public void increment_iter(int idx,int v)//array zero indexed
		{
			idx+=n;
			while(idx>0)
			{
				sgt[idx]+=v;
				idx>>=1;
			}
		}
		public void update(int idx,int v)//array zero indexed
		{
			int diff=v-a[idx];
//			increment_iter(idx, diff);
			a[idx]=v;
			increment_rec(1, n, idx, 1, diff);
		}
		public void increment_range(int l,int r,int v)
		{
			increment_range(l+1, r+1, 1, n, v, 1);
		}
		public void increment_range(int l,int r,int s,int e,int v,int i)
		{
			if(l<=s && r>=e)
			{
				sgt[i]+=v*(r-l+1);
				lazy[i]+=v;
				return;
			}
			if(l>r || r<s)
				return;
			int mid=e+s>>1;
			if(lazy[i]!=0)
				propagate(i,(e-s+1)/2);
			if(l<=mid)
				increment_range(l, r, s, mid, v, i<<1);
			if(e>=mid+1)
				increment_range(l, r, mid+1, e, v, i<<1|1);
			sgt[i]=sgt[i<<1]+sgt[i<<1|1];
		}
		public void propagate(int i,int mid)
		{
			sgt[i*2]+=lazy[i]*mid;
			sgt[i*2+1]+=lazy[i]*mid;
			lazy[i*2]+=lazy[i];
			lazy[i*2+1]+=lazy[i];
			lazy[i]=0;
			return;
		}
	}
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

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

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}

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

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

		double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		boolean hasnext() throws IOException {
			return br.ready();
		}

	}
}
