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
// Don't place your source in a package
import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

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

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("input.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");



        int T=1;
        for(int t=0;t<T;t++){
            int n=Int();
            String s=Str();
            Solution sol=new Solution(out);
            sol.solution(s);
        }
        out.close();

    }

    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution{
    PrintWriter out;
    int INF=Integer.MAX_VALUE;
    int MOD=1000000007;
    public Solution(PrintWriter out){
        this.out=out;
    }


    public void solution(String s) {
        char A[]=s.toCharArray();
        int n=A.length;
        if(n%2!=0){
            out.println(0);
            return;
        }

        int open=0,close=0;
        for(char c:A){
            if(c=='(')open++;
            else close++;
        }

        if(Math.abs(open-close)>2||open==close){
            out.println(0);
            return;
        }


        int mins[]=new int[A.length];
        int dif=0;
        int mn=Integer.MAX_VALUE;
        boolean good[]=new boolean[mins.length];
        for(int i=A.length-1;i>=0;i--){
            if(A[i]=='('){
                dif++;
            }
            else{
                dif--;
            }
            if(dif>0)break;
            good[i]=true;
            mn=Math.min(mn,dif);
            mins[i]=mn;
        }
       // System.out.println(Arrays.toString(mins));



        int res=0;
        Stack<Character>sta=new Stack<>();
        for(int i=0;i<A.length;i++){
            char c=A[i];
            if(c=='('){
                if(sta.size()>0){//change to close
                    if(open>close){
                        int gap=get(mins,i+1);
                        if(sta.size()-1>=gap&&get1(good,i+1))res++;
                    }
                }
                sta.push(c);
            }
            else{
                //change to open
                if(close>open){
                    int gap=get(mins,i+1);
                    if(1+sta.size()>=gap&&get1(good,i+1))res++;
                }
                if(sta.size()==0)break;
                sta.pop();
            }
        }
        out.println(res);
    }

    public int get(int A[],int i){
        if(i>=A.length)return 0;
        return A[i];
    }

    public boolean get1(boolean A[],int i){
        if(i>=A.length)return true;
        return A[i];
    }

}




















