#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int a[1145141]={},n,q,b[1145141]={},c[1145141]={},t1,t2,t3;
#define lowbit(x) (x&(-x))
void adda(int k,int qw)
{
	if(k==0)return;
	for(int i=k;i<=n;i+=lowbit(i))a[i]+=qw;
}
int suma(int k)
{
	if(k==0)return 0;
	int ans=0;
	for(int i=k;i>0;i-=lowbit(i))ans+=a[i];
	return ans;
}
void addb(int k,int qw)
{
	if(k==0)return;
	for(int i=k;i<=n;i+=lowbit(i))
	{
		b[i]+=qw;
	}
}
int sumb(int k)
{
	if(k==0)return 0;
	int ans=0;
	for(int i=k;i>0;i-=lowbit(i))ans+=b[i];
	return ans;
}
signed main()
{
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;++i)
	{
		scanf("%lld",&t1);
		c[t1]++;
	}
	for(int i=1;i<=n;++i)
	{
		addb(c[i],1);
	//	for(int j=1;j<=n;++j)printf("%lld ",b[j]);
	//	puts("");
	}
	for(int i=1;i<=n;++i)
	{
		//adda(i,i*b[i]);
		//a[i]=b[i]*i;
		adda(c[i],c[i]);
	//	for(int j=1;j<=n;++j)printf("%lld ",b[j]);
	//	puts("");
	}
	/*printf("\nc:");
	for(int i=1;i<=n;++i)printf("%lld ",c[i]);
	printf("\nb:");
	for(int i=1;i<=n;++i)printf("%lld ",sumb(i)-sumb(i-1));
	printf("\na:");
	for(int i=1;i<=n;++i)printf("%lld ",suma(i)-suma(i-1));
	puts("");*/
	for(int i=1;i<=q;++i)
	{
		scanf("%lld%lld",&t1,&t2);
		if(t1==1)
		{
			c[t2]++;
			addb(c[t2],1);
			addb(c[t2]-1,-1);
			adda(c[t2],c[t2]);
			adda(c[t2]-1,1-c[t2]);
		}
		else if(t1==2)
		{
			c[t2]--;
			addb(c[t2],1);
			addb(c[t2]+1,-1);
			adda(c[t2],c[t2]);
			adda(c[t2]+1,-1-c[t2]);
		}
		else if(t1==3)
		{
			printf("%lld\n",max(suma(n)-suma(t2)-(sumb(n)-sumb(t2))*t2,0ull));
		}
		/*printf("\nc:");
		for(int i=1;i<=n;++i)printf("%lld ",c[i]);
		printf("\nb:");
		for(int i=1;i<=n;++i)printf("%lld ",sumb(i)-sumb(i-1));
		printf("\na:");
		for(int i=1;i<=n;++i)printf("%lld ",suma(i)-suma(i-1));
		puts("");*/
	}
	return 0;
}