#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4e5+13,INF=0x3f3f3f3f;
struct Splay{
	int fa[N],val[N],siz[N],cnt[N],ch[N][2],root,tot;
	Splay(){root=tot=0;}
	inline bool chk(int x){return ch[fa[x]][1]==x;}
	inline void refresh(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];}
	inline void rotate(int now){
		int f=fa[now],gf=fa[f],k=chk(now),w=ch[now][k^1];
		fa[now]=gf;ch[gf][chk(f)]=now;
		fa[w]=f;ch[f][k]=w;
		fa[f]=now;ch[now][k^1]=f;
		refresh(f),refresh(now);
	}
	inline void splay(int now,int goal=0){
		while(fa[now]!=goal){
			int f=fa[now],gf=fa[f];
			if(gf!=goal){
				if(chk(now)==chk(f)) rotate(f);
				else rotate(now);
			}
			rotate(now);
		}
		if(!goal) root=now;
	}
	inline void insert(int x){
		int now=root,f=0;
		while(now&&val[now]!=x) f=now,now=ch[now][x>val[now]];
		if(now) cnt[now]++,refresh(now);
		else{
			now=++tot;
			ch[now][0]=ch[now][1]=0;
			if(f) ch[f][x>val[f]]=now;
			fa[now]=f;siz[now]=cnt[now]=1;val[now]=x;	
		}
		splay(now);
	}
	inline void find(int x){
		if(!root) return;
		int now=root;
		while(x!=val[now]&&ch[now][x>val[now]]) now=ch[now][x>val[now]];
		splay(now);
	}
	inline int pre(int x){
		find(x);
		if(val[root]<x) return root;
		int now=ch[root][0];
		while(ch[now][1]) now=ch[now][1];
		return now;
	}
	inline int suc(int x){
		find(x);
		if(val[root]>x) return root;
		int now=ch[root][1];
		while(ch[now][0]) now=ch[now][0];
		return now;
	}
	inline void remove(int x){
		int last=pre(x),next=suc(x);
		splay(last),splay(next,last);
		int del=ch[next][0];
		if(cnt[del]>1) cnt[del]--,refresh(del);
		else ch[next][0]=0;
		refresh(next),refresh(last);
	}
	inline int kth(int k){
		int now=root;
		while(1){
			if(siz[ch[now][0]]>=k) now=ch[now][0];
			else if(siz[ch[now][0]]+cnt[now]<k) k-=siz[ch[now][0]]+cnt[now],now=ch[now][1];
			else return now;
		}
	}
	inline void build(){insert(-INF);insert(INF);}
};
Splay T1,T2;
int n,q,a[N],t1,t2;
inline void Print(){
	if(!t1||!t2){puts("0");return;}
	printf("%d\n",T1.val[T1.kth(t1+1)]-T1.val[T1.kth(2)]-T2.val[T2.kth(t2+1)]);
}
int main(){
	scanf("%d%d",&n,&q);
	T1.build(),T2.build();
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	t1=n,t2=n-1;
	for(int i=1;i<=n;++i) T1.insert(a[i]);
	for(int i=1;i<n;++i) T2.insert(a[i+1]-a[i]);
	Print();
	while(q--){
		int op,x;
		scanf("%d%d",&op,&x);
		if(!op){
			int last=T1.val[T1.pre(x)],next=T1.val[T1.suc(x)];
			T1.remove(x);t1--;
			if(last!=-INF) T2.remove(x-last),t2--;
			if(next!=INF) T2.remove(next-x),t2--;
			if(last!=-INF&&next!=INF) T2.insert(next-last),t2++;
		}
		else{
			int last=T1.val[T1.pre(x)],next=T1.val[T1.suc(x)];
			T1.insert(x);t1++;
			if(last!=-INF) T2.insert(x-last),t2++;
			if(next!=INF) T2.insert(next-x),t2++;
			if(last!=-INF&&next!=INF) T2.remove(next-last),t2--;
		}
		Print();
	}
	return 0;
}