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 javafx.util.Pair;
public class Main implements Runnable 
{  
    
    static class Pair implements Comparable <Pair>
    {
        int x,y,ind;
        Pair(int x,int y,int ind)
        {
            this.x=x;
            this.y=y;
            this.ind=ind;
        }
        public int compareTo(Pair p)
        {
            if(x==p.x)
                return Integer.compare(y,p.y);
            else
                return Integer.compare(x,p.x);
        }
    }
    
    public static void main(String[] args)
    {
        new Thread(null, new Main(), "rev", 1 << 29).start();
    }

    public void run()
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1,in,out);
        out.close();
    }
    
    static class Task
    { 
        
        void solve(int testNumber, InputReader in, PrintWriter out)
        {
            int n=in.nextInt();
            String s=in.nextString();
            int ct=0,ans1=0,ans2=0;
            boolean f=true;
            for(int i=0;i<n;i++)
            {
                if(s.charAt(i)=='(')
                {
                    ct++;
                    if(ct>=2)
                        ans1++;
                }
                else
                {
                    ct--;
                    if(ct>-2 && f)
                        ans2++;
                }
                if(ct<=1)
                    ans1=0;
                if(ct<0)
                    f=false;
                if(ct<-2)
                {
                    out.print("0");
                    return;
                }
            }
            out.print((ct==2 && f)?ans1:ct==-2?ans2:"0");
        }
    }
    /*static class OutputWriter
    {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream)
        {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer)
        {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects)
        {
            for(int i=0;i<objects.length;i++)
            {
                if (i!=0)
                {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects)
        {
            print(objects);
            writer.println();
        }

        public void close()
        {
            writer.close();
        }
    }*/

static class InputReader 
{
    private InputStream stream;
    private byte[] buf = new byte[8192];
    private int curChar, snumChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream) 
    {
        this.stream = stream;
    }
 
    public int snext() 
    {
        if(snumChars==-1)
            throw new InputMismatchException();
        if(curChar>=snumChars)
        {
            curChar=0;
            try 
            {
                snumChars = stream.read(buf);                
            } 
            catch(IOException e) 
            {
                throw new InputMismatchException();
            }
            if(snumChars<=0)
                return -1;
        }
        return buf[curChar++];
    }
 
    public int nextInt()
    {
        int c = snext();
        while(isSpaceChar(c))
            c=snext();
        int sgn=1;
        if(c=='-')
        {
            sgn = -1;
            c = snext();
        }
        int res=0;
        do
        {
            if(c<'0' || c>'9')
                throw new InputMismatchException();
            res*=10;
            res+=c-'0';
            c=snext();
            }while(!isSpaceChar(c));
        return res * sgn;
    }
 
    public long nextLong()
    {
        int c = snext();
        while(isSpaceChar(c))
            c=snext();
        int sgn=1;
        if(c=='-')
        {
            sgn=-1;
            c=snext();
        }
        long res=0;
        do{
            if (c<'0' || c>'9')
                throw new InputMismatchException();
            res*=10;
            res+=c-'0';
            c=snext();
        }while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public int[] nextIntArray(int n)
    {
        int a[]=new int[n];
        for(int i=0; i<n; i++)
            a[i]=nextInt();
        return a;
    }

    public long[] nextLongArray(int n)
    {
        long a[]=new long[n];
        for(int i=1; i<n; i++)
            a[i]=nextLong();
        return a;
    }
    public String nextString()
    {
        int c=snext();
        while(isSpaceChar(c))
            c=snext();
        StringBuilder res=new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = snext();
        }while (!isSpaceChar(c));
        return res.toString();
    }
 
    public boolean isSpaceChar(int c)
    {
        if(filter != null)
            return filter.isSpaceChar(c);
        return c==' ' || c=='\n' || c=='\r' || c=='\t' || c==-1;
    }
 
    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}
}