题目描述

给定一个长度为 $n$ （ $n$ 为偶数），由左右括号组成的字符串 $S$ 。

每次操作可以修改 $S$ 中的某个字符，求出最少的操作次数，使 $S$ 变成一个括号串。

我们定义满足以下条件的字符串为括号串。

1.空串是括号串。

2.如果 $A$ 是括号串，$(A)$ 是括号串。

3.如果 $A,B$ 都是括号串，$AB$ 是括号串。

输入格式

第一行输入一个整数 $n$ 。

第二行输入一个长度为 $n$ 的字符串 $S$ ，$S$ 中每个字符为左括号或者右括号。

输出格式

输出一行一个整数，表示最少的操作次数。

输入输出样例 #1

输入 #1

4
())(

输出 #1

2

输入输出样例 #2

输入 #2

2
((

输出 #2

1

输入 #3

3.in

输出 #3

3.out

说明/提示

对于 $30\%$ 的数据， $n \le 10$ 。

对于另外 $30\%$ 的数据，$n \le 10^3$ 。

对于另外 $20\%$ 的数据，$S$ 中仅包含左括号。

对于全部数据， $1 \le n \le 10^6$ ， $n$ 是偶数，$S$ 长度为 $n$ ，而且每个字符为左括号或者右括号。