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 CP {
    static IO io = new IO(System.in);
    static int N;
    static String seq;
    static int[] prefix, suffix;

    public static void main(String[] args) throws Exception {
        int i, j, k;

        N = io.nextInt();
        seq = io.next();

        prefix = new int[N]; suffix = new int[N];
        for (i = 0; i < N; ++i) {
            prefix[i] = seq.charAt(i) == '(' ? 1 : -1;
            if (i > 0) prefix[i] += prefix[i - 1];
            if (prefix[i] < 0) prefix[i] = -7;
        }
        for (i = N - 1; i >= 0; --i) {
            suffix[i] = seq.charAt(i) == ')' ? 1 : -1;
            if (i < N - 1) suffix[i] += suffix[i + 1];
            if (suffix[i] < 0) suffix[i] = -7;
        }

        int count = 0;
        for (i = 0; i < N; ++i) {
            int left = i > 0 ? prefix[i - 1] : 0;
            int right = i < N - 1 ? suffix[i + 1] : 0;
            if (left < 0 || right < 0) continue;
            if ((seq.charAt(i) == '(' ? -1 : 1) == right - left)
                ++count;
        }

        //System.out.println(Arrays.toString(prefix));
        //System.out.println(Arrays.toString(suffix));

        io.println(count);
        io.flush();
    }
}

class IO {
    static byte[] buf = new byte[2048];
    static int index, total;
    static InputStream in;
    static StringBuilder sb = new StringBuilder();


    IO(InputStream is) {
        in = is;
    }

    int scan() throws Exception {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0)
                return -1;
        }
        return buf[index++];
    }

    String next() throws Exception {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan())
            sb.append((char) c);
        return sb.toString();
    }

    int nextInt() throws Exception {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    long nextLong() throws Exception {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+')
            c = scan();
        for (; c >= '0' && c <= '9'; c = scan())
            val = (val << 3) + (val << 1) + (c & 15);
        return neg ? -val : val;
    }

    void print(Object a) {
        sb.append(a.toString());
    }

    void println(Object a) {
        sb.append(a.toString()).append("\n");
    }

    void println() {
        sb.append("\n");
    }

    void flush() {
        System.out.print(sb);
        sb = new StringBuilder();
    }
}