P5640,17pts

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int n,m,a[N],opt,ch,ans,t[N],cnt=3999,lef=4000,pre,flag;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	   scanf("%d",&a[i]);
	while(m--)
	{
		scanf("%d%d",&opt,&ch);
		ans=0;flag=1;
		if(opt==0)
		{
			t[++cnt]=ch;
		}
		else if(opt==1)
		{
			t[--lef]=ch;
		}
	for(int j=lef;j<=cnt;j++){
			flag=1;
			for(int k=lef;k<=j;k++){
				if(t[cnt-j+k]==a[k-lef+1]){
					flag=0;break;
				}
			}
			if(flag==1) ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}