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
in1 = int(input())
in2 = input()
count = 0
series = []

if in1 == 1:
    print(0)
else:
    for x in in2:
        if x == "(":
            series.append(1)
        else:
            series.append(-1)
    
    for x in range(len(series)-1):
        series[x+1] = series[x]+series[x+1]
    
    if series[-1] == 2 and min(series) >= 0:
        count = 0
        for x in range(1, len(series)):
            if series[-x] >= 2:
                if in2[-x] == "(":
                    count += 1
            else:
                break
            
    else:
        if series[-1] == -2 and min(series) >= -2:
            count = 0
            for x in range(len(series)):
                if in2[x] == ")":
                    count += 1
                if series[x] < 0:
                    break
    print(count)
	 		    			 	  				  	  		  	