Background

Note: The time limit for this problem has been changed to 250 ms, and the testdata has been greatly strengthened. This problem forces O2 optimization, and there will be no rejudge. Please resubmit by yourselves.

Because the teachers at School Y are very “toxic”, they required zhouwc to take the midterm exam during the last 3 days before the CSP exam. zhouwc was very angry and decided to do badly on purpose, aiming to finish filling the answer sheet but get everything wrong. Now retcarizy feels zhouwc is too pitiful and wants to help zhouwc solve a problem, but he is too busy, gugugu, so he threw the problem to you.

Problem 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