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 javax.print.DocFlavor;
import javax.swing.text.TextAction;
import javax.swing.text.html.HTMLDocument;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.Inet4Address;
import java.nio.charset.IllegalCharsetNameException;
import java.sql.SQLOutput;
import java.util.*;
import java.util.concurrent.locks.ReentrantReadWriteLock;


public class Main {
    static int[] parent;
    static LinkedList<Integer>[] graph;


    public static void main(String[] args) throws IOException{
        Reader.init(System.in);
        int t = 1;
        while (t-->0) {
            solve();
        }
    }

    static void solve()throws IOException {
        int n = Reader.nextInt();
        String s = Reader.next();
        if (n%2==1){
            System.out.println(-1);
            return;
        }
        char[] arr = s.toCharArray();
        int cnt1 = 0;
        for (int i = 0 ; i < n ; i++){
            if (arr[i]=='('){
                cnt1++;
            }
            else{
                cnt1--;
            }
        }
        if (cnt1!=0){
            System.out.println(-1);
            return;
        }
        Stack<Character> st = new Stack<>();
        for (int i = 0 ; i < n ; i++){
            if (i==0){
                st.add(arr[i]);
            }
            else{
                if (arr[i]=='('){
                    st.push(arr[i]);
                }
                else{
                    if (st.isEmpty()){
                        st.push(arr[i]);
                        continue;
                    }
                    if (st.peek()=='('){
                        st.pop();
                    }
                    else{
                        st.push(')');
                    }
                }
            }
        }
        if (st.size()==0){
            System.out.println(0);
            return;
        }
        st = new Stack<>();
        int ans = 0;
        for (int i =0 ; i < n ; i++){
            if (i==0){
                st.push(arr[i]);
            }
            else{
                if (arr[i]=='('){
                    if (st.isEmpty()){
                        st.push('(');
                        continue;
                    }
                    if (st.peek()==')'){
                        st.pop();
                        ans+=2;
                    }
                    else{
                        st.push(arr[i]);
                    }
                }
                else{
                    if (st.isEmpty()){
                        st.push(')');
                        continue;
                    }
                    if (st.peek()=='('){
                        st.pop();
                    }
                    else{
                        st.push(')');
                    }
                }
            }
        }
        System.out.println(ans);



    }

    public static int stringCompare(String str1, String str2)
    {

        int l1 = str1.length();
        int l2 = str2.length();
        int lmin = Math.min(l1, l2);

        for (int i = 0; i < lmin; i++) {
            int str1_ch = (int)str1.charAt(i);
            int str2_ch = (int)str2.charAt(i);

            if (str1_ch != str2_ch) {
                return str1_ch - str2_ch;
            }
        }

        // Edge case for strings like
        // String 1="Geeks" and String 2="Geeksforgeeks"
        if (l1 != l2) {
            return l1 - l2;
        }

        // If none of the above conditions is true,
        // it implies both the strings are equal
        else {
            return 0;
        }
    }








    static int next(long[] arr, long target)
    {
        int start = 0, end = arr.length - 1;

        int ans = -1;
        while (start <= end) {
            int mid = (start + end) / 2;

            // Move to right side if target is
            // greater.
            if (arr[mid] <= target) {
                start = mid + 1;
            }

            // Move left side.
            else {
                ans = mid;
                end = mid - 1;
            }
        }
        return ans;
    }

    static int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }
    static boolean merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x==y){
            return false;
        }
        parent[x] = y;
        return true;
    }







    public static void sortbyColumn(int arr[][], int col)
    {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1,
                               final int[] entry2) {

                // To sort in descending order revert
                // the '>' Operator
                if (entry1[col] > entry2[col])
                    return 1;
                else
                    return -1;
            }
        });  // End of function call sort().
    }


    static class Node{
        long a;
        int i;
        Node(long a, int i){
            this.a = a;
            this.i = i;
        }
    }

}


class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
class MergeSort
{
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(int arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    // Driver method

}

class Node implements Comparable<Node>{
    int a;
    int b;
    Node (int a , int b){
        this.a = a;
        this.b = b;
    }



    public int compareTo(Node o) {
        if ((this.a%2) == (o.a%2)){
            return (this.b - o.b);
        }
        else{
            return this.a - o.a;
        }
    }
}