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.*;

public class Testation {
	static int n;
	static String str;

	static SegTreeNode[] stree;
	
	static int counter;

	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner console = new Scanner(System.in);
		n = console.nextInt();
		str = console.next();
		solve();
		console.close();
	}

	public static void solve() {
		counter = 0;
		stree = new SegTreeNode[(int) (2 * Math.pow(2, Math.ceil(Math.log(n) / Math.log(2))) - 1)];
		buildST(0, 0, n - 1);
		// updates
		int val;
		for (int i = 0; i<n; i++) {
			if (str.charAt(i) == '(') {
				// change to )
				val = -1;
			}
			else {
				// change to (
				val = 1;
			}
			update(i, val);
			if (stree[0].closed == 0 && stree[0].opened == 0) {
				counter++;
			}
			// undo
			update(i, -val);
		}
		System.out.println(counter);
	}

	public static SegTreeNode buildST(int index, int l, int r) {
		if (l >= r) {
			stree[index] = new SegTreeNode(0, ((str.charAt(l) == '(') ? 1 : 0), ((str.charAt(l) == ')') ? 1 : 0));
			return stree[index];
		}
		int mid = getMid(l, r);
		SegTreeNode child1 = buildST(2 * index + 1, l, mid);
		SegTreeNode child2 = buildST(2 * index + 2, mid + 1, r);
		int minMatched = Math.min(child1.opened, child2.closed);
		int pairs = child1.correctPairs + child2.correctPairs + minMatched;
		int leftOpen = child1.opened + child2.opened - minMatched;
		int rightOpen = child1.closed + child2.closed - minMatched;
		stree[index] = new SegTreeNode(pairs, leftOpen, rightOpen);
		return stree[index];
	}

	public static int getMid(int l, int r) {
		return (l + r) / 2;
	}

	public static SegTreeNode queryUtil(int index, int qs, int qe, int l, int r) {

		if (qs <= l && qe >= r)
			return stree[index];

		if (qs > r || qe < l)
			return new SegTreeNode(0, 0, 0);

		int mid = getMid(l, r);
		SegTreeNode child1 = queryUtil(2 * index + 1, qs, qe, l, mid);
		SegTreeNode child2 = queryUtil(2 * index + 2, qs, qe, mid + 1, r);
		int minMatched = Math.min(child1.opened, child2.closed);
		int pairs = child1.correctPairs + child2.correctPairs + minMatched;
		int leftOpen = child1.opened + child2.opened - minMatched;
		int rightOpen = child1.closed + child2.closed - minMatched;
		stree[index] = new SegTreeNode(pairs, leftOpen, rightOpen);
		return stree[index];
	}

	public static void update(int i, int val) {
		updateUtil(i, val, 0, n - 1, 0);
	}

	public static void updateUtil(int i, int value, int ss, int se, int si) {
		if (i < ss || i > se)
			return;

		if (se == ss) {
			stree[si] = new SegTreeNode(0, (value == 1) ? 1 : 0, (value == -1) ? 1 : 0);
		}

		else {
			int mid = getMid(ss, se);
			updateUtil(i, value, ss, mid, si * 2 + 1);
			updateUtil(i, value, mid + 1, se, si * 2 + 2);
			SegTreeNode child1 = stree[2 * si + 1];
			SegTreeNode child2 = stree[2 * si + 2];
			int minMatched = Math.min(child1.opened, child2.closed);
			int pairs = child1.correctPairs + child2.correctPairs + minMatched;
			int leftOpen = child1.opened + child2.opened - minMatched;
			int rightOpen = child1.closed + child2.closed - minMatched;
			stree[si] = new SegTreeNode(pairs, leftOpen, rightOpen);
		}
	}

}

class SegTreeNode {
	int correctPairs;
	int opened;
	int closed;

	public SegTreeNode(int correctPairs, int opened, int closed) {
		this.correctPairs = correctPairs;
		this.opened = opened;
		this.closed = closed;
	}

	public String toString() {
		return "Correct pairs: " + correctPairs + ", open parend: " + opened + ", closed parend: " + closed + "\n";
	}
}