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


public class e{

    static int n;
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
    static boolean[] visited;
    public static void main(String[] args) {
      MyScanner sc = new MyScanner();
      out = new PrintWriter(new BufferedOutputStream(System.out));

      n = sc.nextInt();
      String s = sc.nextLine();
      int[] arr = new int[n];
      for(int i=0; i<n; i++) {
          arr[i] = (s.charAt(i)==(char)'(') ? 0: 1;
      }
      int[] finale = new int[n];
      int[] diff = new int[n];
      int[] finaldiff = new int[n];
      int count0 = 0;
      int count1 = 0;
      for(int i=0; i<n; i++) {
          if(arr[i]==0) {
              count0++;
          } else {
              count1++;
          }
          diff[i] = count0 - count1;
      }
      if(count0==count1-2) {
          for(int i=0; i<n-1; i++) {
              finale[i] = 1 - arr[n-1-i];
              finaldiff[i] = diff[n-2-i]+2;
          }
          finale[n-1] = 1 - arr[0];
          finaldiff[n-1] = 2;
      } else {
          for(int i=0; i<n; i++) {
              finale[i] = arr[i];
              finaldiff[i] = diff[i];
          }
      }
      int maxindex = -1;
      int count = 0;
      if(finaldiff[n-1]!=2) {
         out.println(0);
      } else {
          for(int i=0; i<n; i++) {
              if(finaldiff[i]==1) {
                  maxindex = i;
              }
          }
          for(int j=maxindex+1; j<n; j++) {
              if(finale[j]==0) {
                  count++;
              }
          }
          boolean output = false;
          for(int i=0; i<n; i++) {
              if(finaldiff[i]<0 && !output) {
                  out.println(0);
                  output = true;
              }
          }
          if(!output) {
            out.println(count);
          }
      }
      
      // Start writing your solution here. -------------------------------------
   
      /*
      int n      = sc.nextInt();        // read input as integer
      long k     = sc.nextLong();       // read input as long
      double d   = sc.nextDouble();     // read input as double
      String str = sc.next();           // read input as String
      String s   = sc.nextLine();       // read whole line as String

      int result = 3*n;
      out.println(result);                    // print via PrintWriter
      */

      // Stop writing your solution here. -------------------------------------
      out.close();
   }

   //-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;
      
   //-----------MyScanner class for faster input----------
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
 
      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() {
          return Integer.parseInt(next());
      }
 
      long nextLong() {
          return Long.parseLong(next());
      }
 
      double nextDouble() {
          return Double.parseDouble(next());
      }
 
      String nextLine(){
          String str = "";
	  try {
	     str = br.readLine();
	  } catch (IOException e) {
	     e.printStackTrace();
	  }
	  return str;
      }

   }
   //--------------------------------------------------------
}