定义一个仅包含括号 $“(”$ 和 $“)”$ 的括号序列为合法序列如下。

1、空串 $“”$ 为合法序列。

2、如果串 $A、B$ 均为合法序列，则 $C=A+B$（即将 $B$ 拼在 $A$ 后面）也是一个合法序列。

3、如果串 $A$ 为合法序列，则串 $C=“(”+A+“)”$（即在 $A$ 的外面套一层括号）也是一个合法序列。

例如，$“( ) ( ) ( ( ) )”$、$“( ( ) ) ( )”$ 均是合法序列，而 $“( ) (”、“( ) ) (”$ 则不是合法序列。

现在给你一个长度为 $N$ 的仅包含括号 $“(”$ 和 $“)”$ 的括号序列 $S$，你每次操作可以交换其中两个括号的位置，求将 $S$ 变成一个合法序列的最少操作次数，无解则输出 $-1$。

输入格式

第一行为一个正整数 $N$。

第二行为一个字符串 $S$。

输出格式

输出最少操作次数，无解则输出 $-1$。

样例一

input

6
)))(((

output

2

explanation

$) ) ) ( ( ( → ( ) ) ( ( ) → ( ) ( ) ( )$

限制与约定

对于 $30\texttt{%}$ 的数据：$1 \leq N \leq 10$。

对于 $60\texttt{%}$ 的数据：$1 \leq N \leq 1000$。

对于 $100\texttt{%}$ 的数据：$1 \leq N \leq 100000$。

时间限制：$1\texttt{s}$

空间限制：$128\texttt{MB}$