题目理解

本题要求我们根据给定的字符串s和数组a，通过最少的修改次数使数组满足字符串的匹配要求。字符串中的每个字符对应数组中的一个元素，具体要求如下：

• '0'：对应元素必须≤0
• '1'：对应元素必须≥0
• 'Z'：对应元素必须=0，且左右相邻元素乘积≥0（边界除外）

解题思路

基本处理步骤

题目内容

小歪拿到了一个长度为 $n$，仅由字符 $'0’$、$'1’$和$'Z’$组成的字符串 $s_1s_2…s_n$。据说，这个字符串是用来匹配数组的。

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

• $s_i$ 为 $'0'$ 时，$a_i≦0$；

• $s_i$ 为 $'1'$时，$a_i≧0$；

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

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

输入描述

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

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

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

输出描述

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

样例1

输入

4
Z0Z0
-1 -2 3 4

输出

3

说明

在这个样例中:

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

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

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

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

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

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

而对于 $s_3$ 的 $'Z’$，此时已经有 $a_2 × a_4 ≥0$ 满足条件。

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

样例2

输入

3
01Z
-9 6 0

输出

0