题目描述

给出一个长度为 $n$ 的括号序列 $T$。每个位置的括号为 $3$ 种颜色其中一个：$0$、$1$ 和 $2$，且可能是左括号或右括号。

允许将 $T$ 中某些括号从 ( 变为 )，反之亦然。但不能改变括号的颜色。我们希望通过零次或多次修改使最终序列满足：

1. 若移除所有 $0$ 颜色括号，剩余括号构成平衡括号序列。
2. 若移除所有 $1$ 颜色括号，剩余括号构成平衡括号序列。

一个括号序列 $S$ 被称为平衡的，当且仅当满足以下条件之一：

1. $S$ 为空序列
2. $S=XY$，其中 $X$ 和 $Y$ 都是非空的平衡括号序列
3. $S=(X)$，其中X是平衡括号序列（注意起始左括号和结尾右括号颜色可以不同）

问是否可能实现？若可以，求出需要最少修改多少个位置的括号。

输入格式

第一行一个正整数，表示 $n$。

接下来一行一个长度为 $n$ 的括号字符串，表示 $T$。

接下来一行 $n$ 个数，第 $i$ 个数 $c_i$ 代表位置 $i$ 的括号的颜色为 $c_i$。

输出格式

一行一个整数表示答案，如果没有方案，输出 -1。

样例 1 输入

5
))))(
0 1 2 2 2

样例 1 输出

4

样例 2 输入

6
(()())
0 0 0 0 0 0

样例 2 输出

0

限制与约定

对于 $100\%$ 的数据，$n\le 2\times 10^5,\forall c_i\in\{0,1,2\}$。

特殊性质A：不存在颜色为 $2$ 的括号。

特殊性质B：不存在颜色为 $1$ 的括号。