#include<map>
#include<queue>
#include<ctime>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
#define eps 1e-9
#pragma GCC optimize(2)
LL read() {
	LL f = 1,x = 0;char s = getchar();
	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
	return f * x;
}
int n,m,i,j,s,o,k;
LL a[MAXN];
//----------------------------------Treap
struct np{int s[2];np(){s[0]=s[1]=0;}np(int A,int B){s[0]=A;s[1]=B;}};
struct tr{
	int s[2],siz,hp,lz;
	LL ky,sm,k2,sm2;
	tr(){s[0]=s[1]=siz=hp=0;ky=sm=k2=sm2=lz=0;}
}tre[MAXN<<1];
int CNT;
inline int newnode(LL key) {
	int x = ++ CNT; tre[x] = tr();
	tre[x].ky = tre[x].sm = tre[x].k2 = tre[x].sm2 = key;
	tre[x].siz = 1; tre[x].hp = rand() *1ll* rand() % 998244353;
	return x;
}
inline int update(int x) {
	int ls = tre[x].s[0],rs = tre[x].s[1];
	tre[x].sm = tre[x].ky + tre[ls].sm + tre[rs].sm;
	tre[x].sm2 = tre[x].k2 + tre[ls].sm2 + tre[rs].sm2 + (tre[ls].sm + tre[rs].sm) *1ll* tre[x].lz;
	tre[x].siz = tre[ls].siz + tre[rs].siz + 1;
	tre[0] = tr(); return x;
}
inline void addtm(int x,int y) {
	if(!x) return ;
	tre[x].k2 += tre[x].ky *1ll* y;
	tre[x].sm2 += tre[x].sm *1ll* y;
	tre[x].lz += y; return ;
}
inline void pushdown(int x) {
	if(!x) return ;
	int ls = tre[x].s[0],rs = tre[x].s[1];
	if(tre[x].lz) {
		addtm(ls,tre[x].lz); addtm(rs,tre[x].lz);
		tre[x].lz = 0;
	}return ;
}
inline np spli1(int x,LL k) {
	np as(0,0); if(!x) return as;
	pushdown(x);
	int d = (tre[x].ky <= k ? 1:0);
	as = spli1(tre[x].s[d],k);
	tre[x].s[d] = as.s[d^1];
	as.s[d^1] = update(x); return as;
}
inline np spli2(int x,int rk) {
	np as(0,0); if(!x) return as;
	pushdown(x); if(rk <= 0) return np(0,x);
	int d = (tre[tre[x].s[0]].siz+1 <= rk ? 1:0);
	if(d) rk -= tre[tre[x].s[0]].siz+1;
	as = spli2(tre[x].s[d],rk);
	tre[x].s[d] = as.s[d^1];
	as.s[d^1] = update(x); return as;
}
inline int merg(int p1,int p2) {
	if(!p1 || !p2) return p1+p2;
	pushdown(p1); pushdown(p2);
	if(tre[p1].hp < tre[p2].hp) {tre[p1].s[1] = merg(tre[p1].s[1],p2);return update(p1);}
	tre[p2].s[0] = merg(p1,tre[p2].s[0]); return update(p2);
}
inline int ins(int x,int y) {
	np p = spli1(x,tre[y].ky);
	addtm(y,tre[p.s[0]].siz); addtm(p.s[1],1);
	return merg(merg(p.s[0],y),p.s[1]);
}
inline int del(int x,LL k) {
	np p1 = spli1(x,k-1);
	np p2 = spli2(p1.s[1],1);
	if(p2.s[0] && tre[p2.s[0]].ky == k) p2.s[0] = 0,addtm(p2.s[1],-1);
	return merg(p1.s[0],merg(p2.s[0],p2.s[1]));
}
inline LL sum(int x,int y) {
	if(!x || !y) return 0ll;
	if(tre[tre[x].s[0]].siz+1 <= y)
		return tre[tre[x].s[0]].sm+tre[x].ky+sum(tre[x].s[1],y-(tre[tre[x].s[0]].siz+1));
	return sum(tre[x].s[0],y);
}
inline LL suf(int x,int y) {
	if(!x || y > tre[x].siz) return 0ll;
	if(tre[tre[x].s[0]].siz+1 < y)
		return suf(tre[x].s[1],y-(tre[tre[x].s[0]].siz+1));
	return tre[tre[x].s[1]].sm+tre[x].ky+suf(tre[x].s[0],y);
}
inline LL sum2(int &x,int y) {
	np p1 = spli2(x,y);
	LL res = tre[p1.s[0]].sm * (1ll+y) - tre[p1.s[0]].sm2;
	x = merg(p1.s[0],p1.s[1]);
	return res;
}
inline LL suf2(int &x,int y) {
	np p1 = spli2(x,y-1);
	LL res = tre[p1.s[1]].sm2 - tre[p1.s[1]].sm *1ll* (y-1ll);
	x = merg(p1.s[0],p1.s[1]);
	return res;
}
// ----------------------------------------------------------------
int root = 0;
inline LL calcu() {
	n = tre[root].siz;
	if(!root || n <= 0) return 0ll;
	int md = n/2,st = 0;
	LL ans = 0;
	for(int i = 19;i >= 0;i --) {
		int ad = st+(1<<i);
		if(ad < md && suf(root,n-ad+1) < sum(root,ad+1)) st = ad;
	}
	if(st) ans += (suf2(root,n-st+1) - sum2(root,st)) * 2ll;
	if((n-1) & 1) {
		int rr = 2*md-st-1;
		LL l1 = sum(root,st+1), r1 = suf(root,n-rr+1);
		ans += r1 - l1;
	}
	else if(n > 1) {
		int rr = 2*md-st;
		LL l1 = sum(root,st+1),r1 = suf(root,n-md+1);
		LL l2 = sum(root,md+1),r2 = suf(root,n-rr+1);
		if(r1 < l2) ans += r1-l1 + r2-l2;
		else ans += r2 - l1;
	}
	return ans;
}
int main() {
//	srand(6223);
	n = read(); m = read();
	for(int i = 1;i <= n;i ++) {
		a[i] = read();
		root = ins(root,newnode(a[i]));
	}
	printf("%lld\n",calcu());
	for(int i = 1;i <= m;i ++) {
		o = read();
		LL nm = read();
		if(o == 1) root = ins(root,newnode(nm));
		else root = del(root,nm);
		printf("%lld\n",calcu());
	}
	return 0;
}
