#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=1e6+7;
int n,q,siz; ull sum;
long long w[N],g[N],P[N<<2],Q;
struct node{
	int t; long long u;
}e[N];
struct Tree{
	ull F[N<<2],G[N<<2],H[N<<2]; int st[N],siz[N<<2],res[N];
	inline void add(int l,int r,int t,int ql,int qr,ull T){
		if(l==ql&&r==qr){
			F[t]=F[t]+siz[t]*T,G[t]+=T,H[t]+=T; return;
		}
		if(G[t]){
			F[t<<1]+=G[t]*siz[t<<1],F[t<<1|1]+=G[t]*siz[t<<1|1];
			G[t<<1]+=G[t],G[t<<1|1]+=G[t],G[t]=0;
		}
		int d=(l+r)>>1;
		if(ql<=d) add(l,d,t<<1,ql,min(d,qr),T);
		if(d+1<=qr) add(d+1,r,t<<1|1,max(d+1,ql),qr,T);
		F[t]=F[t<<1]+F[t<<1|1];
	}
	inline ull getpos(int l,int r,int t,int x){
		ull ans=0;
		while(l!=r){
			ans+=H[t];
			int d=(l+r)>>1;
			if(siz[t<<1]>=x) r=d,t=t<<1;
			else l=d+1,x-=siz[t<<1],t=t<<1|1;
		}
		return ans+H[t];
	}
	inline ull getans(int l,int r,int t,int ql,int qr){
		if(l==ql&&r==qr) return F[t];
		if(G[t]){
			F[t<<1]+=G[t]*siz[t<<1],F[t<<1|1]+=G[t]*siz[t<<1|1];
			G[t<<1]+=G[t],G[t<<1|1]+=G[t],G[t]=0;
		}
		int d=(l+r)>>1; ull ans=0;
		if(ql<=d) ans+=getans(l,d,t<<1,ql,min(d,qr));
		if(d+1<=qr) ans+=getans(d+1,r,t<<1|1,max(d+1,ql),qr);
		return ans;
	}
	inline ull getval(int l,int r,int t,int x){
		ull ans=0;
		while(l!=r&&siz[t]!=x){
			if(G[t]){
				F[t<<1]+=G[t]*siz[t<<1],F[t<<1|1]+=G[t]*siz[t<<1|1];
				G[t<<1]+=G[t],G[t<<1|1]+=G[t],G[t]=0;
			}
			int d=(l+r)>>1;
			if(siz[t<<1]>=x) t=t<<1,r=d;
			else ans+=F[t<<1],x-=siz[t<<1],l=d+1,t=t<<1|1;
		}
		return ans+F[t];
	}
	inline void getsiz(int l,int r,int t,int C,int x){
		st[0]=0;
		t=P[C];
		while(t>0) st[++st[0]]=t,t=t>>1;
		for(int i=st[0];i>=1;i--){
			t=st[i];
			if(G[t]){
				F[t<<1]+=G[t]*siz[t<<1],F[t<<1|1]+=G[t]*siz[t<<1|1];
				G[t<<1]+=G[t],G[t<<1|1]+=G[t],G[t]=0;
			}
		}
		t=P[C];
		siz[t]+=x,F[t]=Q,t=t>>1;
		while(t>0){
			siz[t]+=x,F[t]=F[t<<1]+F[t<<1|1],t=t>>1;
		}
	}
	inline int lowbit(int u){
		return (u&(-u));
	}
	inline void addx(int u,int c){
		while(u<=g[0]) res[u]+=c,u+=lowbit(u);
	}
	inline int getres(int u){
		int sum=0;
		while(u>0) sum+=res[u],u-=lowbit(u); return sum;
	}
}A,B;
inline int F(long long u){
	int l=1,r=g[0];
	while(l<=r){
		int d=(l+r)>>1;
		if(g[d]==u) return d;
		else if(g[d]>u) r=d-1; else l=d+1;
	}
}
inline void add(long long u){
	int x=F(u); Q=u,siz++,sum+=u,A.addx(x,1);
	if(A.getres(x)>1) Q+=A.getpos(1,g[0],1,A.getres(x)-1);
	A.add(1,g[0],1,x,g[0],u);
	A.getsiz(1,g[0],1,x,1);
	x=g[0]-x+1; Q=u,B.addx(x,1);
	if(B.getres(x)>1) Q+=B.getpos(1,g[0],1,B.getres(x)-1);
	B.add(1,g[0],1,x,g[0],u);
	B.getsiz(1,g[0],1,x,1);
}
inline void del(long long u){
	int x=F(u); Q=0,siz--,sum-=u,A.addx(x,-1);
	A.add(1,g[0],1,x,g[0],-u);
	A.getsiz(1,g[0],1,x,-1);
	x=g[0]-x+1; Q=0,B.addx(x,-1);
	B.add(1,g[0],1,x,g[0],-u);
	B.getsiz(1,g[0],1,x,-1);
}
inline void write(ull u){
	if(u>9) write(u/10); putchar(u%10+'0');
}
inline ull getA(int u){
	if(u==0) return u;
	return A.getpos(1,g[0],1,u);
}
inline ull getB(int u){
	if(u==0) return u;
	return B.getpos(1,g[0],1,u);
}
inline ull sol(){
	ull ans=B.F[1];
	int l=0,r=siz/2,pos=siz/2,pot=siz/2;
	if(getA(siz/2+1)>getB(siz/2)){
		ans=ans-A.F[1]; return ans;
	}
	while(l<=r){
		int d=(l+r)>>1;
		if(getA(d+1)<=getB(d)) pos=d,r=d-1; else l=d+1;
	}
	l=siz/2+1,r=siz-1;
	while(l<=r){
		int d=(l+r)>>1;
		if(getA(d+1)<=getB(d)) pot=d,l=d+1; else r=d-1;
	}
	if(pos>0) ans=ans-A.getval(1,g[0],1,pos);
	ans=ans-B.getval(1,g[0],1,pot);
	if(pos>1) ans=ans+B.getval(1,g[0],1,pos-1);
	ans=ans-A.F[1]+A.getval(1,g[0],1,pot+1); return ans;
}
inline long long read(){
	long long num=0; char g=getchar(); while(g<48||57<g) g=getchar();
	while(47<g&&g<58) num=(num<<1)+(num<<3)+g-48,g=getchar(); return num;
}
inline void build(int l,int r,int t){
	if(l==r){
		P[l]=t; return;
	}
	int d=(l+r)>>1;
	build(l,d,t<<1),build(d+1,r,t<<1|1);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("p.txt","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++) w[i]=read(),g[i]=w[i]; g[0]=n;
	for(int i=1;i<=q;i++){
		e[i].t=read(),e[i].u=read(),g[++g[0]]=e[i].u;
	}
	sort(g+1,g+g[0]+1); build(1,g[0],1);
	for(int i=1;i<=n;i++) add(w[i]);
	write(sol()),putchar('\n');
	for(int i=1;i<=q;i++){
		if(e[i].t==1) add(e[i].u); else del(e[i].u); write(sol()),putchar('\n');
	}
	return 0;
}