题目描述

给出一个长度为 $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

输出

4

样例 2

输入

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

输出

0

限制与约定

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

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

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