Description

There are $N$ knights labeled $1$ to $N$ standing in a row. The $i$-th knight has power $P_i$.

The knights are competing in a jousting tournament. To do so, each knight will hold a sword pointing either to the left or to the right. The $i$-th knight will point their sword to the left if $S_i=0$ and to the right if $S_i=1$ where $S$ is a binary string of length $N$.

A joust is defined as the following process:

1. Initially all knights are alive.
2. Let $A$ be the list of knights still alive arranged in increasing order of label and $m$ be the size of $A$.
3. For each $i$ from $1$ to $m$. If the $A_i$-th knight has an adjacent knight with bigger power pointing their sword at the $A_i$-th knight's direction, then mark the $A_i$ knight as $\textbf{dead.}$ Formally the $A_i$-th knight will be marked as dead if one of the following condition is true.
   • $i-1 > 0$ and $P_{A_{i-1}} > P_{A_{i}}$ and $S_{A_{i-1}} = 1$
   • $i+1 \leq m$ and $P_{A_{i+1}} > P_{A_{i}}$ and $S_{A_{i+1}} = 0$
4. Return to step 2 if there is at least one knight in $A$ marked as dead.

Now you are given $Q$ queries, each query are of the form:

• Given integer $x$ ($1 \leq x \leq n$), change $S_x$ to $1-S_x$.

After each query, find the number of knights alive after a joust is performed.

Do note that knights do not stay dead after a joust.

Input Format

The first line contains two space-separated integers $N$ and $Q$ ($1 \le N,Q\le 10^6$) -- the size of $P$ and the number of queries.

The second line contains $N$ space-separated integers $P_1, P_2, \ldots, P_n$ ($1 \le P_i \le N$).

The third line contains a binary string $S$ of length $N$.

Then $Q$ lines follow. Each of the $Q$ lines contains a single integer $x$ ($1 \le x \le N$) denoting a query to change $S_x$ to $1-S_x$.

Output Format

Output $Q$ integers $q_1, q_2, \ldots, q_n$ in order on $Q$ lines, where $q_i$ is the number of knights alive after performing a joust after the $i$-th query.

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

Hint

Note

In the first sample input, after the first query, $S$ becomes 01011.

Initially, the (labels of) the knights alive are $\{1, 2, 3, 4, 5\}$. After one iteration, the knights remaining are $\{1,3,4\}$. After the second iteration, the knights remaining are $\{3, 4\}$. After the third iteration, no new knight dies, so 2 knights remain after a joust.

After the second query, $S$ becomes 01111.

After one iteration, the knights remaining are $\{2,3,4,5\}$. After the second iteration, no new knight dies, so 4 knights remain after a joust.

Scoring

Subtask 1 (6 points): $N,Q\le 500$

Subtask 2 (9 points): $P_i \leq P_{i+1}$ for $1 \leq i < N$

Subtask 3 (17 points): $P_i \neq P_j$ if $i \neq j$ and the answer for each query is guaranteed to be at most $50$.

Subtask 4 (19 points): $P_i \neq P_j$ if $i \neq j$

Subtask 5 (19 points): $N,Q \leq 10000$

Subtask 6 (30 points): No additional constraints