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
//package solution;

import java.io.*;
import java.util.*;

public final class Solution {
    BufferedReader br;
    StringTokenizer stk;

    public static void main(String[] args) throws Exception {
        new Solution().run();
    }
    
    {
        stk = null;
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    long mod = 1000_000_000 + 7;
    StringBuilder res = new StringBuilder(1000005);
    
    void run() throws Exception {
        int n = ni();
        char[] c = nt().toCharArray();
        
        if(n % 2 == 1) {
            System.out.println(0);
            return;
        }
        
        boolean[] canBePrefix = new boolean[n];
        boolean[] canBeSuffix = new boolean[n];
        int[] prefix = new int[n];
        int[] suffix = new int[n];
        
        char open = '(', close = ')';
        for(int i = 0; i < n; i++) {
            if(c[i] == open) {
                prefix[i] = suffix[i] = 1;
            } else {
                prefix[i] = suffix[i] = -1;
            }
        }
        
        for(int i = 1, j = n - 2; i < n; i++, j--) {
            prefix[i] += prefix[i - 1];
            suffix[j] += suffix[j + 1];
        }
        
        for(int i = 0; i < n; i++) {
            if(prefix[i] >= 0) {
                canBePrefix[i] = true;
            } else {
                break;
            }
        }
        for(int i = n - 1; i >= 0; i--) {
            if(suffix[i] <= 0) {
                canBeSuffix[i] = true;
            } else {
                break;
            }
        }
        
        int count = 0;
        for(int i = 1; i < n - 1; i++) {
            if(canBePrefix[i - 1] && canBeSuffix[i + 1]) {
                int pref = prefix[i - 1] + ((c[i] == open) ? -1 : 1);
                int suff = suffix[i + 1] + ((c[i] == open) ? -1 : 1);
                if(pref == Math.abs(suffix[i + 1]) || suff == -prefix[i - 1]) {
                    count++;
                }
            }
        }
        invert(0, c);
        if(ok(c)) {
            count++;
        }
        invert(0, c);
        invert(n - 1, c);
        if(ok(c)) {
            count++;
        }
        
        System.out.println(count);
    }
    
    void invert(int idx, char[] c) {
        char open = '(', close = ')';
        c[idx] = (c[idx] == open) ? close : open;
    }
    
    boolean ok(char[] c) {
        int n = c.length;
        Stack<Character> stack = new Stack<>();
        char open = '(', close = ')';
        for(int i = 0; i < n; i++) {
            if(stack.isEmpty()) {
                stack.push(c[i]);
            } else {
                if(stack.peek() == open && c[i] == close) {
                    stack.pop();
                } else {
                    stack.push(c[i]);
                }
            }
        }
        return stack.isEmpty();
    }
    
    //Reader & Writer
    String nextToken() throws Exception {
        if (stk == null || !stk.hasMoreTokens()) {
            stk = new StringTokenizer(br.readLine(), " ");
        }
        return stk.nextToken();
    }

    String nt() throws Exception {
        return nextToken();
    }

    int ni() throws Exception {
        return Integer.parseInt(nextToken());
    }

    long nl() throws Exception {
        return Long.parseLong(nextToken());
    }
}