背景

注意：本题时限修改至 250ms，并且数据进行大幅度加强。本题强制开启 O2 优化，并且不再重测，请大家自己重新提交。

由于 Y 校的老师非常毒瘤，要求 zhouwc 在 csp 考前最后3天参加期中考，zhouwc 非常生气，决定消极考试，以涂完卡但全错为目标。现在 retcarizy 看 zhouwc 太可怜了，想要帮 zhouwc 解决一个问题，但他自己又太忙了，咕咕咕，于是就把问题甩给了你。

题目描述

给你一个长度为 $n$ 的字符串 $S$。

有 $m$ 个操作，保证 $m\le n$。

你还有一个字符串 $T$，刚开始为空。

共有两种操作。

第一种操作：

在字符串 $T$ 的末尾加上一个字符。

第二种操作：

在字符串 $T$ 的开头加上一个字符。

每次操作完成后要求输出有几个 $l \in [1,|T|]$ 满足以下条件：

对于 $\forall i \in [1,l]$ 有 $T_{|T|-l+i} \ne S_{i}$

Tip：字符串下标从 $1$ 开始。$|T|$ 表示 $T$ 的长度。

输入格式

第一行两个正整数 $n,m$。

第二行 $n$ 个正整数，用空格隔开，第 $i$ 个整数表示 $S_i$。

接下来 $m$ 行，每行两个数字 $opt,ch$，$opt=0$ 表示在 $T$ 的末尾加一个字符 $ch$，$opt=1$ 表示在 $T$ 的开头加一个字符 $ch$。

输出格式

共 $m$ 行，每行一个非负整数表示第 $m$ 操作后的输出。

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

0
1
1

提示

注意：本题采用捆绑测试，只有当你通过一个 subtask 的所有点后，你才能拿到这个 subtask 的分数。

对于所有的数据 $n \leq 10^6,m \leq 3.3333 \times 10^4,|\Sigma|\leq10^3,S_i \in [1,|\Sigma|]$。($\Sigma$ 表示字符集)

subtask1($17\%$)：$m \leq 333$。

subtask2($33\%$)：$m \leq 3333$。

subtask3($20\%$)：$|\Sigma|\leq2$。

subtask4($30\%$)：无特殊条件。

样例解释：

第一次操作后，$T=\texttt1$,

$l=1$ 时 $T_1=S_1$，所以答案为 $0$。

第二次操作后，$T=\texttt{21}$，

$l=1$ 时，$T_2=S_1$；

$l=2$ 时，$T_1\ne S_1$，$T_2\ne S_2$，所以答案为 $1$。

第三次操作后，$T=\texttt{213}$，

$l=1$ 时，$T_3\ne S_1$；

$l=2$ 时，$T_2=S_1$；

$l=3$ 时，$T_3=S_3$，所以答案为 $1$。