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.InputStreamReader;
import java.io.BufferedReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.*;

public class E {
    final FastScanner in = new FastScanner();
    final PrintWriter out = new PrintWriter(System.out);
    
    void runTest() {
        int n = in.nextInt();
        String s = in.next();
        if (n == 1) {
            out.println(0);
            return;
        }
        int[] pre = new int[n], suf = new int[n];
        boolean[] pc = new boolean[n], sc = new boolean[n];
        int op = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') op++;
            else op--;
            pre[i] = op;
            pc[i] = op >= 0 && (i == 0 || pc[i - 1]);
        }
        op = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == ')') op++;
            else op--;
            suf[i] = op;
            sc[i] = op >= 0 && (i == n - 1 || sc[i + 1]);
        }
        int ct = 0;
        if (sc[1] && s.charAt(0) == ')' && suf[1] == 1) ct++;
        if (pc[n - 2] && s.charAt(n - 1) == '(' && pre[n - 2] == 1) ct++;
        for (int i = 1; i < n - 1; i++) {
            if (!pc[i - 1] || !sc[i + 1]) continue;
            if (s.charAt(i) == '(' && pre[i - 1] == suf[i + 1] + 1) ct++;
            else if (s.charAt(i) == ')' && pre[i - 1] + 1 == suf[i + 1]) ct++;
        }
        out.println(ct);
    }
    
    void doTask() {
        int tests = 1;
        while (tests-- > 0) {
            runTest();
        }
        in.close();
        out.close();
    }
    
    public static void main(String[] args) throws IOException { new E().doTask(); }
    public static class FastScanner {
        BufferedReader buffReader;
        StringTokenizer tokenizer;
        public FastScanner() { buffReader = new BufferedReader(new InputStreamReader(System.in), 32768); }
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreElements()) {
                try { tokenizer = new StringTokenizer(buffReader.readLine()); } 
                catch (IOException e) { e.printStackTrace(); }
            }
            return tokenizer.nextToken();
        }
        int nextInt() { return Integer.parseInt(next()); }
        long nextLong() { return Long.parseLong(next()); }
        double nextDouble() { return Double.parseDouble(next()); }
        String nextLine(){ 
            String str = "";
            try { str = buffReader.readLine(); } 
            catch (IOException e) { e.printStackTrace(); }
            return str;
        }
        void close() {
            try { buffReader.close(); } 
            catch (IOException e) { e.printStackTrace(); }
        }
    }
}