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.awt.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Random;
import java.util.StringTokenizer;

public class Main {

    String fileName = "";
    int[][] steps = {{0,1}, {1, 0}};
    int INF = Integer.MAX_VALUE / 10 - 123123;
    //////////////////////    SOLUTION   SOLUTION  SOLUTION    //////////////////////////////

    static int checkBit(int mask, int bit) {
        return (mask >> bit) & 1;
    }


    void solve() throws IOException {
        int n = readInt();
        char[] s = readString().toCharArray();
        int[] b = new int[n];
        b[0] = s[0] == ')' ? -1 : 1;
        for (int i=1; i<n; ++i){
            b[i] = b[i - 1] + (s[i] == ')' ? -1 : 1);
        }
        int[] prefMin = new int[n];
        int[] suffMin = new int[n];

        prefMin[0] = Math.min(0, b[0]);
        for (int i=1; i<n; ++i){
            prefMin[i] = Math.min(prefMin[i-1], b[i]);
        }

        suffMin[n-1] = Math.min(n + 100, b[n-1]);
        for (int i=n-2; i>=0; --i){
            suffMin[i] = Math.min(suffMin[i+1], b[i]);
        }

        int ans = 0;
        for (int i=0; i<n; ++i){
            if (s[i] == '('){
                if (prefMin[i] >= 0 && suffMin[i] >= 2 && b[n - 1] == 2) {
                    ans++;
                    //out.println(i + 1);
                }
            }else{
                if ((i == 0 || prefMin[i-1] >= 0) && b[i] >= -2 && prefMin[i] >= -2 && suffMin[i] >= -2 && b[n - 1] == -2) {
                    //out.println(i + 1);
                    ans++;
                }
            }
        }
        out.println(ans);
    }


    ////////////////////////////////////////////////////////////



    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }
    long gcd(long a, long b){
        return b == 0 ? a : gcd(b, a%b);
    }
    long binPow(long a, long pow, long MODULO){
        if (pow == 0) return 1;
        if (pow % 2 == 1) {
            return a * binPow(a, pow - 1, MODULO);
        } else {
            long c = binPow(a, pow / 2, MODULO);
            return c * c % MODULO;
        }
    }

    int minInt(int... values) {
        int min = Integer.MAX_VALUE;
        for (int value : values) min = Math.min(min, value);
        return min;
    }

    int maxInt(int... values) {
        int max = Integer.MIN_VALUE;
        for (int value : values) max = Math.max(max, value);
        return max;
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Main().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    };

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";

    Main() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken(delim);
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }
    byte readByte() throws NumberFormatException, IOException {
        return Byte.parseByte(readString());
    }
    int[] readIntArray (int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }

    Integer[] readIntegerArray (int n) throws NumberFormatException, IOException {
        Integer[] a = new Integer[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }

    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}