Description

You are given a string $S$ of length $n$.

There are $m$ operations, and it is guaranteed that $m \le n$.

You also have a string $T$, which is empty at the beginning.

There are two types of operations.

The first type of operation:

Append one character to the end of string $T$.

The second type of operation:

Prepend one character to the beginning of string $T$.

After each operation, you need to output how many $l \in [1,T.size]$ satisfy the following condition:

For $\forall i \in [1,l]$, we have $T_{T.size-l+i} \ne S_{i}$.

$Tip:$ String indices start from 1. $T.size$ denotes the length of $T$.

Input Format

The first line contains two positive integers $n,m$.

The second line contains $n$ positive integers separated by spaces. The $i$-th integer represents $S_i$.

Next, there are $m$ lines, each containing two numbers $opt,ch$. $opt=0$ means appending a character $ch$ to the end of $T$, and $opt=1$ means prepending a character $ch$ to the beginning of $T$.

Output Format

Output $m$ lines. Each line contains one non-negative integer representing the answer after the $m$-th operation.

10 3
1 2 3 1 2 3 2 3 2 3
0 1
1 2
0 3

0
1
1

Hint

Note: This problem uses bundled tests. You can get the score of a subtask only after you pass all test points of that subtask.

For all testdata, $n \leq 10^6,m \leq 3.3333 \times 10^4,|\sum|\leq10^3,S_i \in [1,|\sum|]$. ($\sum$ denotes the alphabet)

subtask 1 $(17\%)$: $m \leq 333$.

subtask 2 $(33\%)$: $m \leq 3333$.

subtask 3 $(20\%)$: $|\sum|\leq2$.

subtask 4 $(30\%)$: no special constraints.

Sample Explanation:

After the first operation, $T="1"$.

When $l=1$, $T[1]=S[1]$, so the answer is 0.

After the second operation, $T="21"$.

When $l=1$, $T[2]=S[1]$.

When $l=2$, $T[1]!=S[1]$, $T[2]!=S[2]$, so the answer is 1.

After the third operation, $T="213"$.

When $l=1$, $T[3]!=S[1]$.

When $l=2$, $T[2]=S[1]$.

When $l=3$, $T[3]=S[3]$, so the answer is 1.

Translated by ChatGPT 5