#include<bits/stdc++.h>
using namespace std;
const int N=4e4+100;
int n,m;
int s[N];
int t[N];
int vis[N];
int rf[N];
int l=4000;
int r=4001;
struct node
{
	int opt;
	int ch;
}e[N];
int f[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&e[i].opt,&e[i].ch);
	}
	for(int i=1;i<=m;i++)
	{
		int opt,ch;
		opt=e[i].opt;
		ch=e[i].ch;
		if(opt==0)
		{
			t[r]=ch;
			r++;
			if(ch!=s[1])
			{
				f[i]++;
			}
			f[i]+=f[i-1];
			for(int j=2;j<=i;j++)
			{
				if(ch==s[j])
				{
					if(vis[j-1])
					{
						f[i]--;
					}
				}
			}
			for(int j=1;j<=n;j++) rf[j]=vis[j];
			if(ch!=s[1])
			{
				vis[1]=1;
			}
			else vis[1]=0;
			for(int j=2;j<=i;j++)
			{
				if(ch==s[j])
				{
					vis[j]=0;
				}
				else
				{
					if(rf[j-1]) vis[j]=1;
					if(!rf[j-1]) vis[j]=0;
				}
			}
			cout<<f[i]<<endl;
//			for(int j=1;j<=m;j++) cout<<vis[j]<<" ";
//			cout<<endl;
			continue;
		}
		else if(opt==1)
		{
			t[l]=ch;
			l--;
			f[i]=f[i-1];
			int flag=0;
			for(int j=1;j<=i;j++)
			{
				if(s[j]==t[l+j])
				{
					flag=1;
					break;
				}
			}
			if(!flag)
			{
				f[i]++;
				vis[i]=1;
			}
			cout<<f[i]<<endl;
			continue;
		}
	}
	return 0;
}
/*
4 4
3 2 1 4
0 1
0 2
0 3
0 4
*/