说明

时间限制：1 Sec 内存限制：256 MB 输入文件：parentheses.in 输出文件：parentheses.out

“合法的括号序列”定义如下：

1. 空字符串是合法的括号序列。

2. 若字符串 $s$ 是合法的括号序列，则字符串 $(s)$ 也是合法的括号序列。

3. 若字符串 $s$ 和 $t$ 均为合法的括号序列，则字符串 $st$ 也是合法的括号序列。

例如，$()$、$(())$、$()()$、$(())()$、$(((())()()))$ 等均为合法的括号序列。

现给定一个由 $($ 和 $)$ 组成、长度为 $N$ 的字符串 $S$。对于 $1 \le i \le N$，将 $S$ 中从第 $1$ 个字符到第 $i$ 个字符的连续子串记为$S_i$。

取 $S_1, S_2, \cdots, S_N$ 这些子串，按任意顺序拼接得到字符串 $T$。定义 $f(T)$ 为“$T$ 的子序列中，属于正确括号序列的字符串的最大长度”。这里“子序列”是指从 $T$ 中删除部分字符后，剩余字符保持原有顺序拼接而成的字符串。

请找出 $f(T)$ 的最大值。

输入格式

第一行一个整数 $N$。

第二行一个由 $($ 和 $)$ 组成、长度为 $N$ 的字符串 $S$。

输出格式

一个整数，表示 $f(T)$ 的最大值。

样例

样例 1

3
)((

4

样例说明：各子串定义如下：$S_1=)$、$S_2=)($、$S_3=)(($。

1. 若按 $S_2 + S_1 + S_3$ 的顺序拼接，得到的字符串 $T=)())(($。在 $T$ 的所有子序列中，属于正确括号序列的字符串最大长度为 $2$，因此 $f(T)=2$。

2. 若按 $S_3 + S_1 + S_2$ 的顺序拼接，得到的字符串 $T=)(())($。在 $T$ 的所有子序列中，属于正确括号序列的字符串最大长度为 $4$，因此 $f(T)=4$。

不存在能使 $f(T) \gt 4$ 的 $T$，因此 $f(T)$ 的最大值为 $4$。

样例 2

3
)))

0

样例 3

10
(((()))()(

34

数据范围

对于 8% 的数据，$N \le 8$；

对于 100% 的数据，$1 \le N \le 10^5$。