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.util.*;
import java.io.*;

import static java.lang.System.in;

public class Main {
    public static void main(String[] args)throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(),left = 0, right = 0;
        char[] s = sc.next().toCharArray();
        if(n==1){
            System.out.println(0);
            return;
        }
        int[] asFir = new int[n],asSec = new int[n];
        asFir[0] = s[0]=='('?1:-1;
        left = s[0]=='('?1:-1;
        for(int i=1;i<n;i++){
            if(asFir[i-1]<0) asFir[i] = -1;
            else{
                left += s[i]=='('?1:-1;
                asFir[i] = Math.max(-1,left);
            }
        }
        right = s[n-1]==')'?1:-1;
        asSec[n-1] = s[n-1]==')'?1:-1;
        for(int i=n-2;i>=0;i--){
            if(asSec[i+1]<0) asSec[i] = -1;
            else{
                right += s[i]==')'?1:-1;
                asSec[i] = Math.max(-1,right);
            }
        }
        int ans = 0;
        if(s[0]==')'&&asSec[1]==1) ans++;
        if(s[n-1]=='('&&asFir[n-2]==1) ans++;
        for(int i=1;i<n-1;i++){
            if(asFir[i-1]<0||asSec[i+1]<0) continue;
            if(s[i]=='('){
                if(asFir[i-1]==1+asSec[i+1]) ans++;
            } else{
                if(asFir[i-1]+1==asSec[i+1]) ans++;
            }
        }
        System.out.println(ans);
    }
}
