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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String[] args) throws UnsupportedEncodingException, IOException, Exception {
        Reader.init(System.in);
        StringBuilder out = new StringBuilder();
        int n = Reader.nextInt();
        String str = Reader.nextLine();
        int[] l = new int[n], r = new int[n];
        boolean[] lf = new boolean[n], rf = new boolean[n];
        Arrays.fill(lf, true);
        Arrays.fill(rf, true);
        for(int i = 0, cnt = 0; i < n; i++) {
           l[i] = cnt;
           if(i > 0) {
                if(cnt < 0 || !lf[i - 1])
                    lf[i] = false;
            }
            if(str.charAt(i) == '(')
                cnt++;
            else
                cnt--;
        }
        for(int i = n - 1, cnt = 0; i > -1; i--) {
            r[i] = cnt;
            if(i < n - 1) {
                if(cnt < 0 || !rf[i + 1])
                    rf[i] = false;
            }
            if(str.charAt(i) == ')')
               cnt++;
            else
               cnt--; 
        }
        
//        for(int i = 0; i < n; i++)
//            System.out.println(l[i] + " " + r[i] + " " + lf[i] + " " + rf[i]);
        
        int res = 0;
        for(int i = 0; i < n; i++)
            if(str.charAt(i) == '(') {
                if(r[i] >= 0 && l[i] - 1 == r[i] && lf[i] && rf[i])
                    res++;
            } else {
                if(l[i] >= 0 && r[i] - 1 == l[i] && lf[i] && rf[i])
                    res++;
            }
        out.append(res).append('\n');
        PrintWriter pw = new PrintWriter(System.out);
        pw.print(out);
        pw.close();
    }

}

class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) throws UnsupportedEncodingException {
        reader = new BufferedReader(
                new InputStreamReader(input, "UTF-8"));
        tokenizer = new StringTokenizer("");
    }

    static void init(String url) throws FileNotFoundException {
        reader = new BufferedReader(new FileReader(url));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

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

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

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

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