题目描述

薯条哥拿到了一个长度为 $n$，仅由字符 $0$、$1$和$Z$组成的字符串 $s_1,s_2,…,s_n$。据说，这个字符串是用来匹配数组的。

我们称由 $n$ 个整数组成的数组$\left \{a_1,a_2,...,a_n \right \}$满足匹配字符串 $s= s_1,s_2,…,s_n$ 的要求，当且仅当对于每个 $i(1\le i\le n)$有:

$s_i$ 为 $0$ 时，$a_i\le 0$；

$s_i$ 为 $1$时，$a_i\ge 0$；

$s_i$ 为 $Z$ 时，$a_i=0$，且 $a_{i-1}\times a_{i+1}\ge 0$（如果 $i=1$ 或 $i=n$ ，则没有这个限制）。

你可以对数组中的任意元素进行修改，每个修改操作可以将该元素改为任意整数。求最少需要修改多少个元素，使得修改后的数组满足上述匹配要求。

输入描述

第一行输入一个整数 $n(1 \le n < 2\times 10^5)$代表匹配长度。

第二行输入一个长度为 $n$ 的字符串 $s$，字符串仅由 $0$、$1$ 和 $Z$三种字符组成。

第三行输入 $n$ 个整数 $a_1,a_2,...,a_n(-10^6 \le a_i\le 10^6)$ 代表数组中的元素。

输出描述

输出一个整数，代表最少需要修改的元素个数。

样例1

输入

4
Z0Z0
-1 -2 3 4

输出

3

样例解释

在这个样例中:

对于第一个位置，由于 $s_1=Z$，所以 $a_1$ 应当 $= 0$，将其修改。

对于第二个位置，由于 $s_2 =0$，所以 $a_2$ 应当 $\le 0$，此时, $a_2$ 已经满足条件，不需要修改。

对于第三个位置，由于 $s_3 =Z$，所以 $a_3$ 应当 $= 0$，将其修改

对于第四个位置，由于 $s_4 =0$，所以 $a_4$ 应当 $\le 0$，不妨将其修改为 $-4$。

至此，数组修改了 $3$ 次，为 $\left \{ 0,-2,0,-4 \right \}$。检查每一个 $Z$，发现：

对于 $S_1$ 的 $Z$，没有额外条件;

而对于 $s_3$ 的 $Z$，此时已经有 $a_2 \times a_4 \ge 0$ 满足条件。

所以数组被 $s$ 匹配。我们可以证明，在这个样例中，至少需要修改 $3$ 个元素。

样例2

输入

3
01Z
-9 6 0

输出

0