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

public class AlmostRegularBrackets {
    static BufferedReader _in = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer _stk;
    static String next() {
        try {
            while (_stk == null || !_stk.hasMoreTokens())
                _stk = new StringTokenizer(_in.readLine());

            return _stk.nextToken();
        } catch(Exception ex) {
            throw new RuntimeException("Failed reading input", ex);
        }
    }
    static int nextInt() { return Integer.parseInt(next()); }
    static long nextLong() { return Long.parseLong(next()); }
    static double nextDouble() { return Double.parseDouble(next()); }

    public static void main(String [] args) throws IOException {
        int N = nextInt();
        String seq = next();

        int[] sum = new int[N];
        sum[0] = toNum(seq.charAt(0));
        for(int i=1; i<N; i++)
            sum[i] = sum[i-1]+toNum(seq.charAt(i));

        int[] minFrom = new int[N];
        minFrom[N-1] = sum[N-1];
        for(int i=N-2; i>=0; i--) {
            minFrom[i] = Math.min(sum[i], minFrom[i+1]);
        }

        int total = 0;
        boolean negLeft = false;
        for(int i=0; i<N && !negLeft; i++) {
            int shift = seq.charAt(i)=='(' ? -2 : +2;

            if(sum[i]+shift>=0 && sum[N-1]+shift==0 && (i+1>=N || minFrom[i+1]+shift>=0) )
                total++;

            negLeft |= sum[i]<0;
        }

        System.out.println(total);
    }

    static int toNum(char br) {
        return br=='(' ? 1 : -1;
    }
}