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.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= (long)Math.pow(10,9)+7;
    long fac[]= new long[3000];
    public  void solve() throws IOException 
    {
        int n = readInt();

        String s = readString();

        int pre[]= new int[n+1];
        

        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='(')
                pre[i+1]= pre[i]+1;
            else
                pre[i+1]= pre[i]-1;
        }

        if(pre[n]!=2&&pre[n]!=-2)
        {
            out.println(0);
        }
        else
        {
           int left[]= new int[n+1];
           
           for(int i=1;i<=n;i++)
           {
            left[i]=Math.min(pre[i],left[i-1]);
           }
           int right[]= new int [n+1];
           right[n]=pre[n];
           for(int i=n-1;i>=1;i--)
           {
            right[i]= Math.min(right[i+1],pre[i]);
           }
           int count=0;

           if(pre[n]==-2)
           {
            for(int i=0;i<n;i++)
            {
                if(s.charAt(i)==')'&&left[i]==0&&right[i+1]==-2)
                {
                    count++;
                }
            }
           }
           else
           {
            for(int i=0;i<n;i++)
            {
                if(s.charAt(i)=='('&&left[i]==0&&right[i+1]==2)
                {
                    count++;
                }
            }
           }
           out.println(count);
        }

    }

    public int seg(int seg[], int left, int right, int index, int val)
    {
        if(left==right)
        {
            seg[index]=1;
            return 1;
        }
        int mid = left+(right-left)/2;

        if(val<=mid)
        {
            seg(seg,left,mid,2*index+1,val);
        }
        else
        {
            seg(seg,mid+1,right,2*index+2,val);
        }
        seg[index]= seg[2*index+1]+seg[2*index+2];
        return seg[index];
    }
    public int val(int seg[], int left , int right, int l , int r,int index)
    {
            if(left>r||right<l)
            {
               return 0;
            }
            int mid = left+(right-left)/2;
            if(left>=l&&right<=r)
            return seg[index];

            return val(seg,left,mid,l,r,2*index+1)+val(seg,mid+1,right,l,r,2*index+2);
    }
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int val ;
    int color;
    
    edge(int u, int v)
    {
       this.val=u;
       this.color=v;
    }
    public int compareTo(edge e)
    {
        return this.val-e.val;
    }
}