说明

有 $N$ 个骑士，编号 $1$ 到 $N$，站成一排。第 $i$ 个骑士的力量为 $P_i$。

骑士们正在参加一场马上枪术锦标赛。为此，每个骑士需要将他的剑指向左侧或右侧。若 $S_i = 0$，则第 $i$ 个骑士将剑指向左侧；若 $S_i = 1$，则指向右侧。其中 $S$ 是一个长度为 $N$ 的二进制字符串。

一场 枪术对决 定义为如下过程：

1. 初始时所有骑士均存活。
2. 令 $A$ 为按编号升序排列的仍存活骑士的列表，$m$ 为 $A$ 的大小。
3. 对于 $i$ 从 $1$ 到 $m$，如果第 $A_i$ 号骑士存在一个 力量更大 的相邻骑士，且该相邻骑士的剑尖指向第 $A_i$ 号骑士的方向，则将第 $A_i$ 号骑士标记为 死亡。形式化地，若满足以下任一条件，则第 $A_i$ 号骑士将被标记为死亡：
   • $i-1 > 0$ 且 $P_{A_{i-1}} > P_{A_{i}}$ 且 $S_{A_{i-1}} = 1$
   • $i+1 \leq m$ 且 $P_{A_{i+1}} > P_{A_{i}}$ 且 $S_{A_{i+1}} = 0$
4. 如果列表 $A$ 中至少有一个骑士被标记为死亡，则返回步骤 2。

现在，你将收到 $Q$ 个询问，每个询问的形式如下：

• 给定整数 $x$ （$1 \leq x \leq n$），将 $S_x$ 变为 $1-S_x$。

在每次询问之后，请计算经过一场枪术对决后，仍存活的骑士数量。

注意，骑士不会在上一场对决中死亡后继续死亡（即每次对决都是独立的，初始状态均为所有骑士存活）。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $Q$ （$1 \le N, Q \le 10^6$）—— 表示数组 $P$ 的长度和询问的数量。

第二行包含 $N$ 个以空格分隔的整数 $P_1, P_2, \ldots, P_n$ （$1 \le P_i \le N$）。

第三行包含一个长度为 $N$ 的二进制字符串 $S$。

接下来 $Q$ 行，每行包含一个整数 $x$ （$1 \le x \le N$），表示将 $S_x$ 变为 $1-S_x$ 的询问。

输出格式

按顺序输出 $Q$ 行，每行一个整数 $q_i$，其中 $q_i$ 表示在第 $i$ 次询问之后，执行一场枪术对决后仍存活的骑士数量。

5 3
2 1 3 4 3
11011
1
3
4

2
4
2

10 5
10 1 2 3 8 9 4 5 7 6
0111100110
10
5
6
5
1

5
5
3
6
1

提示

注释

在第一个样例输入中，第一次询问后，$S$ 变为 01011。

初始时，存活骑士（的编号）为 $\{1, 2, 3, 4, 5\}$。经过第一轮迭代后，剩余的骑士为 $\{1,3,4\}$。经过第二轮迭代后，剩余的骑士为 $\{3, 4\}$。经过第三轮迭代后，没有新的骑士死亡，因此一场枪术对决后剩余 2 名骑士。

第二次询问后，$S$ 变为 01111。

经过第一轮迭代后，剩余的骑士为 $\{2,3,4,5\}$。经过第二轮迭代后，没有新的骑士死亡，因此一场枪术对决后剩余 4 名骑士。

计分

子任务 1 （$6$ 分）： $N, Q \le 500$

子任务 2 （$9$ 分）： 对于 $1 \le i < N$，有 $P_i \leq P_{i+1}$

子任务 3 （$17$ 分）： 若 $i \neq j$，则 $P_i \neq P_j$，且保证每个询问的答案不超过 $50$

子任务 4 （$19$ 分）： 若 $i \neq j$，则 $P_i \neq P_j$

子任务 5 （$19$ 分）： $N, Q \leq 10000$

子任务 6 （$30$ 分）： 无额外限制

翻译由 DeepSeek 完成