using namespace std;
#include <bits/stdc++.h>
#define N 200005
#define ll long long
int n,Q;
ll a[N];
struct Node *null,*rt;
struct Node{
	Node *fa,*c[2];
	ll v,sz,s0,s1;
	bool getson(){return fa->c[0]!=this;}
	void upd(){
		sz=c[0]->sz+c[1]->sz+1;
		s0=c[0]->s0+c[1]->s0+v;
		s1=c[0]->s1+c[1]->s1+(v+c[1]->s0)*(c[0]->sz+1);
	}
	void rotate(){
		Node *y=fa,*z=y->fa;
		if (z!=null)
			z->c[y->getson()]=this;
		else
			rt=this;
		int k=getson();
		fa=z;
		y->c[k]=c[k^1],c[k^1]->fa=y;
		c[k^1]=y,y->fa=this;
		y->upd(),upd();
	}
	void splay(Node *t=null){
		for (;fa!=t;rotate())
			if (fa->fa!=t)
				getson()!=fa->getson()?rotate():fa->rotate();
	}
};
Node *newnode(ll v=0){
	Node *nw=new Node;
	*nw={null,null,null,v,1,v,v};
	return nw;
}
Node *build(int l,int r){
	if (l>r) return null;
	int mid=l+r>>1;
	Node *t=newnode(a[mid]);
	t->c[0]=build(l,mid-1);t->c[0]->fa=t;
	t->c[1]=build(mid+1,r);t->c[1]->fa=t;
	t->upd();
	return t;
}
void insert(ll v){
	if (rt==null){
		rt=newnode(v);
		return;
	}
	Node *t=rt;
	while (1){
		if (v<t->v){
			if (t->c[0]!=null)
				t=t->c[0];
			else{
				t->c[0]=newnode(v),t->c[0]->fa=t;
				t=t->c[0];
				t->splay();
				break;
			}
		}
		else{
			if (t->c[1]!=null)
				t=t->c[1];
			else{
				t->c[1]=newnode(v),t->c[1]->fa=t;
				t=t->c[1];
				t->splay();
				break;
			}
		}
	}
	t->upd();
}
void erase(ll v){
	Node *t=rt;
	while (1){
		if (v==t->v)
			break;
		if (v<t->v)
			t=t->c[0];
		else
			t=t->c[1];
	}
	t->splay();
	if (t->c[0]==null && t->c[1]==null)
		rt=null;
	else if (t->c[0]!=null){
		Node *p=t->c[0];
		while (p->c[1]!=null) p=p->c[1];
		p->splay(t);
		p->c[1]=t->c[1],t->c[1]->fa=p;
		p->upd();
		rt=p,rt->fa=null;
	}
	else
		rt=t->c[1],rt->fa=null;
	delete t;
}
Node *find(int k){
	Node *t=rt;
	while (1){
		if (k==t->c[0]->sz+1)
			return t;
		if (k<=t->c[0]->sz)
			t=t->c[0];
		else
			k-=t->c[0]->sz+1,t=t->c[1];
	}
}
struct info{ll sz,s0,s1;};
info query(int l,int r){
	if (l>r) return {0,0,0};
	if (l==1 && r==rt->sz)
		return {rt->sz,rt->s0,rt->s1};
	if (l==1){
		Node *t=find(r+1);
		t->splay();
		return {t->c[0]->sz,t->c[0]->s0,t->c[0]->s1};
	}
	Node *t=find(l-1);
	t->splay();
	return {t->c[1]->sz,t->c[1]->s0,t->c[1]->s1};
}
ll calc(){
	if (rt==null) return 0;
	int n=rt->sz;
	int l=(1+n)/2,r=n-2,k=n-1;
	if (query(1,l).s0>query(n-(l-1)+1,n).s0)
		k=-1;
	else{
		while (l<=r){
			int mid=l+r>>1;
			info tmps=query(1,mid+1),tmpt=query(n-mid+1,n);
			if (tmps.s0>tmpt.s0)
				r=(k=mid)-1;
			else
				l=mid+1;
		}
	}
	ll ans=0;
	if (n-k<=k){
		ans+=query(1,n-k).s1+query(n-k+1,n).s0*(n-k);
		ans-=query(1,n).s0*(n+1)-(query(k+1,n).s1+query(k+1,n).s0*k)-query(1,k).s0*(k+1);
		ans*=2;
		ans+=query(n-k+1,n).s0-query(1,n-k).s0;
//		for (int i=k+1;i<n;++i)
//			ans+=2*(query(n-i+1,n).s0-query(1,i).s0);
	}
	else{
		ans+=query(1,n).s1;
		ans-=query(1,n).s0*(n+1)-query(1,n).s1;
//		for (int i=1;i<n;++i)
//			ans+=query(n-i+1,n).s0-query(1,i).s0;
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&Q);
	for (int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	null=new Node;
	*null={null,null,null,0,0,0};
	rt=build(1,n);
	printf("%lld\n",calc());
	while (Q--){
		int ty;
		ll v;
		scanf("%d%lld",&ty,&v);
		if (ty==1)
			insert(v);
		else
			erase(v);
		printf("%lld\n",calc());
	}
	return 0;
}














