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.*;
import java.math.BigInteger;
import java.text.*;
public class Main {
    static long mod = 1000_000_007;
    static long mod1 = 998244353;
    static boolean fileIO = false;
    static boolean memory = true;
    static FastScanner f;
    static FileWriter fw;
    static PrintWriter pw;
    static double eps = (double)1e-6;
    static int oo = Integer.MAX_VALUE;
 
    // N = 1 or N = max ?
    // longs vs. ints ?
    // max / min ?

    static class RMQ {

        public int t[];
        
        public RMQ(int n , int arr[]) {
            t = new int[2 * n];
            for (int i = 0; i < n; ++i) t[n + i] = arr[i];

            for (int i = n - 1; i >= 0; --i) {
                t[i] = Math.min(t[i << 1] , t[(i << 1) + 1]);
            }
        }

        public void update(int pos , int val , int n) {
            for (t[pos += n] = val; pos > 1; pos /= 2) t[pos / 2] = t[pos] + t[pos ^ 1];
        }

        public int query(int l , int r , int n) {
            
            int ans = Integer.MAX_VALUE;
            if (l >= r) return ans;

            for (l += n , r += n; l < r; l /= 2 , r /= 2) {
                if ((l & 1) == 1) ans = Math.min(ans , t[l++]);
                if ((r & 1) == 1) ans = Math.min(ans , t[--r]);
            }

            return ans;
        }
    }

    public static void solve() throws Exception {
        int n = f.ni();
        
        char s[] = f.next().toCharArray();

        int a[] = new int[n];


        for (int i = 0; i < n; ++i) {
            if (s[i] == '(') a[i] = i == 0 ? 1 : a[i - 1] + 1;
            else a[i] = i == 0 ? -1 : a[i - 1] - 1;
        }

        RMQ rmq = new RMQ(n , a);

        int ans = 0;
        if (Math.abs(a[n - 1]) == 2) {
            
            for (int i = 0; i < n; ++i) {
                if (s[i] == '(') {
                    int suff = rmq.query(i , n , n);
                    int pre = rmq.query(0 , i , n);
                    if (suff >= 2 && pre >= 0 && a[n - 1] == 2) ++ans;
                }

                else {
                    int suff = rmq.query(i , n , n);
                    int pre = rmq.query(0 , i , n);
                    if (suff >= -2 && pre >= 0 && a[n - 1] == -2) ++ans;
                }
            }
        }

        pn(ans);
    }    
 
    public static void main(String[] args)throws Exception {
        if(memory) new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "", 1 << 28).start();
        else new Main().run();
    }
        
/******************************END OF MAIN PROGRAM*******************************************/
    void run()throws Exception {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            f = new FastScanner("");
            pw = new PrintWriter(System.out);
            fw = new FileWriter("!out.txt");
        }
        else {
            f = new FastScanner();
            pw = new PrintWriter(System.out);
            fw = new FileWriter("!out.txt");
        }
        //
        int t = 1;
        int tt = 1;
 
        while(t --> 0) {
            //p("Case #" + (tt++) + ": ");
            //fw.write("\n");
            solve();
        }
        
        pw.flush(); 
        pw.close(); 
    }
 
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner(String str) throws Exception {
            try {
                br = new BufferedReader(new FileReader("!a.txt"));
            }
            catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
 
        public String next()throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        public int ni() throws IOException {return Integer.parseInt(next());}
 
        public long nl() throws IOException {return Long.parseLong(next());}
 
        public String nextLine() throws IOException {return br.readLine();}
 
        public double nd() throws IOException {return Double.parseDouble(next());}
    }
 
    public static void pn(Object... o) {for(int i = 0; i < o.length; ++i) pw.print(o[i] + (i + 1 < o.length ? " ": "\n"));}
    public static void p(Object... o) {for(int i = 0; i < o.length; ++i) pw.print(o[i] + (i + 1 < o.length ? " " : ""));}
    public static void pni(Object... o) {for(Object obj : o) pw.print(obj + " "); pw.println(); pw.flush();}
    public static int gcd(int a,int b){if(b==0)return a;else{return gcd(b,a%b);}}
    public static long gcd(long a,long b){if(b==0l)return a;else{return gcd(b,a%b);}}
    public static long lcm(long a,long b){return (a*b/gcd(a,b));}
    public static long pow(long a,long b){long res=1;while(b>0){if((b&1)==1)res=res*a;b>>=1;a=a*a;}return res;}
    public static int pow(int a,int b){int res=1;while(b>0){if((b&1)==1)res=res*a;b>>=1;a=a*a;}return res;}
    public static long mpow(long a,long b, long m){long res=1;while(b>0){if((b&1)==1)res=((res%m)*(a%m))%m;b>>=1;a=((a%m)*(a%m))%m;}return res;}
    public static long mul(long a , long b , long mod){return ((a%mod)*(b%mod)%mod);}
    public static long adp(long a , long b){return ((a%mod)+(b%mod)%mod);}
    public static int dig(long a){int cnt=0;while(a>0){a/=10;++cnt;}return Math.max(1,cnt);}
    public static int dig(int a){int cnt=0;while(a>0){a/=10;++cnt;}return Math.max(1,cnt);}
    public static boolean isPrime(long n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(long i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
    public static boolean isPrime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
    public static TreeSet<Long> factors(long n){TreeSet<Long> hs=new TreeSet<Long>();for(long i=1;i<=(long)Math.sqrt(n);i++){if(n%i==0){hs.add(i);hs.add(n/i);}}return hs;}
    public static HashSet<Integer> factors(int n){HashSet<Integer> hs=new HashSet<Integer>();for(int i=1;i<=(int)Math.sqrt(n);i++){if(n%i==0){hs.add(i);hs.add(n/i);}}return hs;}
    public static TreeSet<Long> pf(long n){TreeSet<Long> ff=factors(n);TreeSet<Long> ans=new TreeSet<Long>();for(Long i:ff)if(isPrime(i))ans.add(i);return ans;}
    public static HashSet<Integer> pf(int n){HashSet<Integer> ff=factors(n);HashSet<Integer> ans=new HashSet<Integer>();for(Integer i:ff)if(isPrime(i))ans.add(i);return ans;}
    public static int gnv(char c){return Character.getNumericValue(c);}
    public static void sort(int[] a){ArrayList<Integer> l=new ArrayList<>();for(int i:a)l.add(i);Collections.sort(l);for(int i=0;i<a.length;++i)a[i]=l.get(i);}
    public static void sort(long[] a){ArrayList<Long> l=new ArrayList<>();for(long i:a)l.add(i);Collections.sort(l);for(int i=0;i<a.length;++i)a[i]=l.get(i);}
    public static void sort(ArrayList<Integer> a){Collections.sort(a);}
}