#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=4000010;
typedef long long ll;
int n,q,op[maxn],cnt,l,r,mid,L,R,siz[maxn];
#define lc (o<<1)
#define rc (o<<1|1)
ll sum[maxn],sum2[maxn],p[maxn],v[maxn],a[maxn];
void update(int o,int l,int r,int x,int v)
{
	siz[o]+=v;sum[o]+=a[x]*v;
	if(l==r){sum2[o]=a[l]*siz[o]*(siz[o]+1)/2;return;}
	int mid=(l+r)>>1;
	if(x<=mid)update(lc,l,mid,x,v);
	else update(rc,mid+1,r,x,v);
	sum2[o]=(sum2[lc]+sum2[rc]+siz[lc]*sum[rc]);
}
ll qq(int o,int l,int r,int k,int op)
{
	if(l==r)return (ll)min(k,siz[o])*sum[o];
	int mid=(l+r)>>1;
	if(op==1)
	{
		if(siz[lc]>=k)return qq(lc,l,mid,k,op);
		else
		{
			ll ret=qq(rc,mid+1,r,k-siz[lc],op);
			return sum[lc]+ret;
		}
	}
	else
	{
		if(siz[rc]>=k)return qq(rc,mid+1,r,k,op);
		else
		{
			ll ret=qq(lc,l,mid,k-siz[rc],op);
			return sum[rc]+ret;
		}
	}
}
ll query(int o,int l,int r,int k,int op,ll&v)
{
	if(l==r){v=a[l]*min(k,siz[o])*(min(k,siz[o])+1)/2;return min(k,siz[o])*sum[o];}
	int mid=(l+r)>>1;
	if(op==1)
	{
		if(siz[lc]>=k)return query(lc,l,mid,k,op,v);
		else
		{
			ll ret=query(rc,mid+1,r,k-siz[lc],op,v);
			v=v+sum2[lc]+siz[lc]*ret;
			return sum[lc]+ret;
		}
	}
	else
	{
		if(siz[rc]>=k)return query(rc,mid+1,r,k,op,v);
		else
		{
			ll ret=query(lc,l,mid,k-siz[rc],op,v);
			v=v+sum2[rc]+(k-siz[rc])*sum[rc];
			return sum[rc]+ret;
		}
	}
}
ll calc(int x)
{
	ll t1,t2,t3;
	t2=query(1,1,cnt,x,1,t1);
	t2=(x+1)*t2-t1;
	query(1,1,cnt,x,-1,t3);
	return t3-t2;
}
void solve()
{
	ll t=0;
	L=R=0;
	l=0;r=siz[1]-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		ll t1=qq(1,1,cnt,mid+1,1),t2=qq(1,1,cnt,mid,-1);
		if(t1<=t2)L=mid,r=mid-1;else l=mid+1;
	}
	l=0;r=siz[1]-1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		ll t1=qq(1,1,cnt,mid+1,1),t2=qq(1,1,cnt,mid,-1);
		if(t1<=t2)R=mid+1,l=mid+1;else r=mid-1;
	}
	if(R==0)
	{
		printf("%lld\n",calc(siz[1]));
	}
	else
	{
		printf("%lld\n",calc(L-1)+calc(siz[1])-calc(R)+query(1,1,cnt,R,-1,t)-query(1,1,cnt,L,1,t));
	}
}
signed main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%lld",p+i),a[++cnt]=p[i];
	for(int i=1;i<=q;i++){scanf("%d%lld",op+i,v+i);if(op[i]==1)a[++cnt]=v[i];}
	sort(a+1,a+cnt+1);cnt=unique(a+1,a+cnt+1)-a-1;
	for(int i=1;i<=n;i++)p[i]=lower_bound(a+1,a+cnt+1,p[i])-a,update(1,1,cnt,p[i],1);
	solve();
	for(int i=1;i<=q;i++)
	{
		if(op[i]==1)update(1,1,cnt,lower_bound(a+1,a+cnt+1,v[i])-a,1);
		else update(1,1,cnt,lower_bound(a+1,a+cnt+1,v[i])-a,-1);
		solve();
	}
	return 0;
}