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.*;

public class AlmostRegularBrackerSequence {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(inp, out);
        out.close();
    }

    static class Solver {
        private int case1(char[] s, int n) {
            // ( -> )
            int val = 0, count = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == '(') val++;
                else val--;
                if (val < 0) return 0;
                else if (val == 0 || val == 1) count = 0;
                else if (s[i] == '(') count++;
            }
            return count;
        }

        private int case2(char[] s, int n) { // ) -> (
            int val = 0, count = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == '(') val++;
                else val--;
                if (val == -1) {
                    s[i] = '(';
                    count++;
                    if (correct(s)) return count;
                    else return 0;
                } else if (s[i] == ')') count++;
            }
            return count;
        }

        private boolean correct(char[] s) {
            int val = 0;
            for (char c: s) {
                if (c == '(') val++;
                else val--;
                if (val < 0) return false;
            }
            return val == 0;
        }

        private void solve(InputReader inp, PrintWriter out) {
            int n = inp.nextInt();
            char[] s = inp.next().toCharArray();
            int l = 0, r = 0;
            for (char c: s) {
                if (c == '(') l++;
                else r++;
            }
            if (l - r == 2) {
                out.print(case1(s, n));
            } else if (r - l == 2){
                out.print(case2(s, n));
            } else {
                out.print(0);
            }

        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

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