#include <bits/stdc++.h>
using namespace std;
const int maxn=200100;
const int inf=1e9;
const int mod=998244353;
typedef long long ll;
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define rep(i, x, y) for(int i = x; i <= y; ++i)
struct node {
    int l,r;
    ll sum,sum_i,cnt;
}t[maxn*8];
int n,num,op[maxn];
ll a[maxn],b[maxn],key[maxn*2],tot;
void pushup(int o)
{
    t[o].cnt=t[2*o].cnt+t[2*o+1].cnt;
    t[o].sum=t[2*o].sum+t[2*o+1].sum;
    t[o].sum_i=t[2*o].sum_i+t[2*o+1].sum_i+t[2*o].cnt*t[2*o+1].sum;
}
void modify(int o,int l,int r,int p,int x)
{
    if (l==r) {
        t[o].cnt+=x;
        t[o].sum_i=1LL*(1+t[o].cnt)*t[o].cnt/2*key[p];
        t[o].sum=t[o].cnt*key[p];
        return ;
    }
    int mid=(l+r)/2;
    if (p<=mid) modify(2*o,l,mid,p,x);
    else modify(2*o+1,mid+1,r,p,x);
    pushup(o);
}
pair<ll,ll> getxth(int o,int x)
{
    if (t[o].l==t[o].r) {
        return mp(x*key[t[o].l],1LL*x*(x+1)/2*key[t[o].l]);
    }
    if (x<=t[2*o].cnt) return getxth(2*o,x);
    pair<ll,ll> s2=getxth(2*o+1,x-t[2*o].cnt);
    //printf("%lld\n",t[2*o].cnt);
    return mp(t[2*o].sum+s2.fi,t[2*o].sum_i+s2.se+t[2*o].cnt*s2.fi);
}
ll get(int p)
{
    pair<ll,ll> s1=getxth(1,p+1),s2=getxth(1,n-p);
    //printf("fi===%lld %lld %lld %d\n",s1.fi,s2.fi,t[1].cnt,n);
    return s1.fi-(t[1].sum-s2.fi);
}
ll getans()
{
    if (n==0) return 0;
    int l,r,p,mid;
    ll ans,num;
    l=0; r=(n-1)/2; p=r+1;
    //printf("p=%d %d\n",p,get(0));
   // return 0;
    while (l<=r) {
        mid=(l+r)/2;
        if (get(mid)<=0) {r=mid-1; p=mid;}
        else l=mid+1;
    }p--;
    //printf("p=%d %d\n",p,get(0));
    pair<ll,ll> s1=getxth(1,p+1),s2=getxth(1,n-p);
    ans=(p+2)*s1.fi-s1.se;
    num=t[1].sum-s2.fi;
    ans-=t[1].sum_i-s2.se-num*(n-p);
    ans*=2; if (n%2)ans-=max(get((n-1)/2),0LL);
    return tot-ans;
}
void build(int o,int l,int r)
{
    int mid=(l+r)/2;
    t[o].l=l; t[o].r=r;
    if (l==r) return ;
    build(2*o,l,mid); build(2*o+1,mid+1,r);
}
int main()
{
    int q;
   // freopen("text.in","r",stdin);
    scanf("%d%d",&n,&q); num=0; tot=0;
    for (int i=1;i<=n;i++) {
        scanf("%lld",&a[i]); key[++num]=a[i];
    }
    for (int i=1;i<=q;i++) {
        scanf("%d%lld",&op[i],&b[i]); key[++num]=b[i];
    }
    sort(key+1,key+num+1);
    num=unique(key+1,key+num+1)-key-1;
    //printf("num=%d\n",num);
    for (int i=1;i<=n;i++) {
        tot+=a[i];
        a[i]=lower_bound(key+1,key+num+1,a[i])-key;
    }
    for (int i=1;i<=q;i++) {
        b[i]=lower_bound(key+1,key+num+1,b[i])-key;
    }
    //printf("sum=%lld\n",tot);
    build(1,1,num);
    for (int i=1;i<=n;i++) modify(1,1,num,a[i],1);
    printf("%lld\n",getans());
   //  return 0;
    for (int i=1;i<=q;i++) {
        if (op[i]==1) {
            modify(1,1,num,b[i],1); ++n; tot+=key[b[i]];
        }else {
            modify(1,1,num,b[i],-1); --n; tot-=key[b[i]];
        }
        printf("%lld\n",getans());
    }
    return 0;
}
