A bracketed sequence is called correct (regular) if by inserting "+" and "1" you can get a well-formed mathematical expression from it. For example, sequences "(())()", "()" and "(()(()))" are correct, while ")(", "(()" and "(()))(" are not.

The teacher gave Dmitry's class a very strange task — she asked every student to come up with a sequence of arbitrary length, consisting only of opening and closing brackets. After that all the students took turns naming the sequences they had invented. When Dima's turn came, he suddenly realized that all his classmates got the correct bracketed sequence, and whether he got the correct bracketed sequence, he did not know.

Dima suspects now that he simply missed the word "correct" in the task statement, so now he wants to save the situation by modifying his sequence slightly. More precisely, he can the arbitrary number of times (possibly zero) perform the reorder operation.

The reorder operation consists of choosing an arbitrary consecutive subsegment (substring) of the sequence and then reordering all the characters in it in an arbitrary way. Such operation takes l nanoseconds, where l is the length of the subsegment being reordered. It's easy to see that reorder operation doesn't change the number of opening and closing brackets. For example for "))((" he can choose the substring ")(" and do reorder ")()(" (this operation will take 2 nanoseconds).

Since Dima will soon have to answer, he wants to make his sequence correct as fast as possible. Help him to do this, or determine that it's impossible.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^6) — the length of Dima's sequence.

The second line contains string of length n, consisting of characters "(" and ")" only.

Output

Print a single integer — the minimum number of nanoseconds to make the sequence correct or "-1" if it is impossible to do so.

Examples

Input


8
))((())(


Output


6


Input


3
(()


Output


-1

Note

In the first example we can firstly reorder the segment from first to the fourth character, replacing it with "()()", the whole sequence will be "()()())(". And then reorder the segment from the seventh to eighth character, replacing it with "()". In the end the sequence will be "()()()()", while the total time spent is 4 + 2 = 6 nanoseconds.
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;
 
import static java.lang.Math.*;
 
public class MakingString implements Runnable 
{
    static class InputReader 
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        public InputReader(InputStream stream) 
        {
            this.stream = stream;
        }
        
        public int read()
        {
            if (numChars==-1) 
                throw new InputMismatchException();
            
            if (curChar >= numChars) 
            {
                curChar = 0;
                try
                {
                    numChars = stream.read(buf);
                }
                catch (IOException e)
                {
                    throw new InputMismatchException();
                }
                
                if(numChars <= 0)               
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() 
        {
            int c = read();
            
            while(isSpaceChar(c)) 
                c = read();
            
            int sgn = 1;
        
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            
            int res = 0;
            do
            {
                if(c<'0'||c>'9') 
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c)); 
        
            return res * sgn;
        }
        
        public long nextLong() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            long res = 0;
            
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public double nextDouble() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') 
            {
                c = read();
                double m = 1;
                while (!isSpaceChar(c))
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
    
        public String readString() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = read();
            } 
            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 String next()
        {
            return readString();
        }
        
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
	
	
	// if modulo is required set value accordingly
	public static long[][] matrixMultiply2dL(long t[][],long m[][])
	{
		long res[][]= new long[t.length][m[0].length];
		
		for(int i=0;i<t.length;i++)
		{
			for(int j=0;j<m[0].length;j++)
			{
				res[i][j]=0;
				for(int k=0;k<t[0].length;k++)
				{
					res[i][j]+=t[i][k]+m[k][j];
				}
			}
		}
		
		return res;
	}
	
	static long combination(long n,long r)
	{
		long ans=1;
		for(long i=0;i<r;i++)
		{
			ans=(ans*(n-i))/(i+1);
		}
		return ans;
	}
	static int mat(String a,String b)
	{
	    int count=0;
	    for(int i=0;i<a.length();i++)
	    {
	        if(a.charAt(i)!=b.charAt(i))
	            count++;
	        
	    }
	    
	    return count;
	}
	
	static int accumulate(int arr[], int first, 
                                     int last) 
    { 
        int init = 0; 
        for (int i = first; i< last; i++) { 
            init = init + arr[i]; 
        } 
      
        return init; 
    } 
  
    // Returns true if it is possible to divide  
    // array into two halves of same sum.  
    // This function mainly uses combinationUtil() 
    static Boolean isPossible(int arr[], int n) 
    { 
        // If size of array is not even. 
        if (n % 2 != 0) 
            return false; 
  
        // If sum of array is not even. 
        int sum = accumulate(arr, 0, n); 
        if (sum % 2 != 0) 
            return false; 
  
        // A temporary array to store all  
        // combination one by one int k=n/2; 
        int half[] = new int[n/2]; 
  
        // Print all combination using temporary 
        // array 'half[]' 
        return combinationUtil(arr, half, 0, n - 1, 
                                0, n, sum); 
    } 
  
    /* arr[] ---> Input Array 
    half[] ---> Temporary array to store current  
                combination of size n/2 
    start & end ---> Staring and Ending indexes in arr[] 
    index ---> Current index in half[] */
    static Boolean combinationUtil(int arr[], int half[],  
                                   int start, int end, 
                                   int index, int n, 
                                   int sum) 
    { 
        // Current combination is ready to  
        // be printed, print it 
        if (index == n / 2) { 
            int curr_sum = accumulate(half, 0 , n/2); 
            return (curr_sum + curr_sum == sum); 
        } 
  
        // replace index with all possible elements.  
        // The condition "end-i+1 >= n/2-index" makes 
        // sure that including one element at index  
        // will make a combination with remaining 
        // elements at remaining positions 
        for (int i = start; i <= end && end - i + 1 >=  
                                  n/2 - index; i++) { 
            half[index] = arr[i]; 
            if (combinationUtil(arr, half, i + 1, end,  
                                 index + 1, n, sum)) 
                return true; 
        } 
  
        return false; 
    } 
    public static void main(String args[]) throws Exception 
    {
        new Thread(null, new MakingString(),"MakingString",1<<27).start();
    }
	// **just change the name of class from Main to reuquired**
    public void run()
    {
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
		
	    
	    
	    
	        int n = sc.nextInt();
	        String st=sc.next();
	        int count1=0;
	        int count2=0;
	        int c1=0;
	        int c2=0;
	        int sum=0;
	        if(n%2!=0)
	        {
	            System.out.println(-1);
	        }
	        else
	        {
	            
	            for(int i=0;i<st.length();i++)
	                {
	                    if(count1<=0 && count2==0 && st.charAt(i)=='(')
	                        {
	                            count1--;
	                            c2++;
	                            
	                        }
	                    else if(st.charAt(i)==')')
	                        {
	                            count1++;
	                            c1++;
	                        }
	                    else 
	                        {
	                            count2++;
	                            c2++;
	                        }
	                   if(count1-count2==0)
	                    {
	                        sum=sum+count1+count2;
	                        count1=0;
	                        count2=0;
	                    }
	                   
	                   
	               
	                }
	        if(c1-c2==0)
	            System.out.println(sum);
	        else
	            System.out.println(-1);
	        }
	        
	      
	    
        
    
	    
	    
        System.out.flush();
        w.close();
        
    }
}