#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
struct node;
int size(node *x);
int height(node *x);
ll sum(node *x);
ll sig(node *x);
struct node{
	node *l,*r;
	ll x,y,v,g;//a_i;i*a_i
	int s,h,f;
	node(ll _v=0){l=r=NULL;x=y=v=g=_v;f=0;s=1;h=rand()<<15|rand();}
	void pushup(){
		x=sum(l)+sum(r)+v;
		y=sig(l)+sig(r)+g;
		s=size(l)+size(r)+1;
	}
	void down(){
		if(!f)return;
		if(l)l->y+=l->x*f,l->f+=f,l->g+=l->v*f;
		if(r)r->y+=r->x*f,r->f+=f,r->g+=r->v*f;
		f=0;
	}
}Sta[400005],*NOW=Sta;
node* New(ll _v=0){*NOW=node(_v);return NOW++;}
int size(node *x){return x?x->s:0;}
ll sum(node *x){return x?x->x:0;}
ll sig(node *x){return x?x->y:0;}
ll val(node *x){return x?x->v:0;}
node* L(node *x){return x?x->l:NULL;}
node* R(node *x){return x?x->r:NULL;}
typedef pair<node*,node*> A;
A split(node *x,ll v){
	if(!x)return A(NULL,NULL);
	A y;x->down();
	if(val(x)<=v){
		y=split(x->r,v);
		x->r=y.first;
		y.first=x;
		x->pushup();
	}else{
		y=split(x->l,v);
		x->l=y.second;
		y.second=x;
		x->pushup();
	}return y;
}
A split_(node *x,int v){
	if(!x)return A(NULL,NULL);
	if(!v)return A(NULL,x);
	A y;x->down();
	if(size(x->l)<v){
		y=split_(x->r,v-size(x->l)-1);
		x->r=y.first;
		y.first=x;
		x->pushup();
	}else{
		y=split_(x->l,v);
		x->l=y.second;
		y.second=x;
		x->pushup();
	}return y;
}
node* merge(node *x,node *y){
	if(!x||!y)return x?x:y;
	x->down();y->down();
	if(x->h<y->h){
		x->r=merge(x->r,y);
		x->pushup();
		return x;
	}else{
		y->l=merge(x,y->l);
		y->pushup();
		return y;
	}
}
int s,m,S;
node *root;
void insert(ll v){
	A x=split(root,v);node *t=New(v);
	if(x.second)++x.second->f,x.second->y+=x.second->x,x.second->g+=x.second->v;
	t->g=t->y=(size(x.first)+1)*v;
	root=merge(merge(x.first,t),x.second);
}
void erase(ll v){
	A x=split(root,v),y=split(x.first,v-1);
	if(x.second)--x.second->f,x.second->y-=x.second->x,x.second->g-=x.second->v;
	root=merge(y.first,x.second);
}
ll pre(int v,node *n=root){
	if(!v||!n)return 0;
	n->down();
	if(v==size(n))return sum(n);
	if(v<=size(n->l))return pre(v,n->l);
	if(v==size(n->l)+1)return sum(n->l)+n->v;
	return sum(n->l)+n->v+pre(v-size(n->l)-1,n->r);
}
ll suf(int v){return sum(root)-pre(S-v);}
ll pre_i(int v){
	A x=split_(root,v);
	ll t=(v+1)*sum(x.first)-sig(x.first);
	root=merge(x.first,x.second);
	return t;
}
ll suf_i(int v){
	A x=split_(root,S-v);
	ll t=sig(x.second)-(S-v)*sum(x.second);
	root=merge(x.first,x.second);
	return t;
}
ll query(){S=size(root);
	int w=0,mid=S>>1;
	for(int i=18;i--;){
		int d=1<<i|w;
		if(d<mid&&pre(d+1)>suf(d))w=d;	
	}ll ans=0;
	if(w)ans=suf_i(w)-pre_i(w)<<1;
	if(~S&1)ans+=suf(S-w-1)-pre(w+1);
	else if(S>1){
		ll lx=pre(w+1),rx=suf(mid),ly=pre(mid+1),ry=suf(S-w-1);
		if(rx<ly)ans+=rx+ry-lx-ly;
		else ans+=ry-lx;
	}return ans;
}
ll a[200005];int tot,H;
node* build(int l,int r){
	if(l>r)return NULL;
	int mid=l+r>>1;
	node *v=New(a[mid]);
	v->h=INT_MAX/H*++tot+rand()-16384;
	v->g=a[mid]*mid;
	v->l=build(l,mid-1);
	v->r=build(mid+1,r);--tot;
	v->pushup();return v;
}
void pr(ll x){
	if(x>9)pr(x/10);
	putchar(x-x/10*10^'0');
}
int main(){srand(214);
	s=read;m=read;
	for(int i=1;i<=s;++i)a[i]=read;H=log2(s)+1;
	sort(a+1,a+s+1);
	root=build(1,s);
	printf("%lld\n",query());
	for(int i=1;i<=m;++i){
		if(read&1)insert(read);
		else erase(read);
		pr(query());putchar('\n');
	}
	return 0;
}
