Description

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

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

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

共有两种操作。

第一种操作：

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

第二种操作：

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

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

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

$Tip:$字符串下标从1开始。$T.size$表示T的长度。

Input Format

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

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

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

Output Format

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

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

0
1
1

Hint

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

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

subtask1$(17\%)$:$m \leq 333$

subtask2$(33\%)$:$m \leq 3333$

subtask3$(20\%)$:$|\sum|\leq2$

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

样例解释：

第一次操作后，$T="1"$,

$l=1$时$T[1]=S[1]$，所以答案为0

第二次操作后，$T="21"$,

$l=1$时，$T[2]=S[1]$

$l=2$时，$T[1]!=S[1]$,$T[2]!=S[2]$所以答案为1

第三次操作后，$T="213"$,

$l=1$时，$T[3]!=S[1]$;

$l=2$时，$T[2]=S[1]$;

$l=3$时，$T[3]=S[3]$所以答案为1