#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
using namespace std;
typedef long long ll;
//const int N = 2500;
//const int N = 400100;
const int N = 400100;
const int M = N + N;
vector<ll> elms;
//__int128 LEN;
ll VL[N], a[N];
ll cnt[4 * N], pref_sums[4 * N], suf_sums[4 * N], sum[4 * N];
ll psh_pref[4 * N], psh_suf[4 * N];
ll fi_glob, se_glob, ALL = 0;
bool INS[N];
int TP[N];
int n, q;

void build(int v, int l, int r){
    if (l == r) {
        if (INS[l]){
            cnt[v] = 1;

            sum[v] = elms[l];

            fi_glob += elms[l];

            pref_sums[v] = fi_glob;
            suf_sums[v] = se_glob;

            se_glob -= elms[l];
        }

        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    cnt[v] = cnt[v + v] + cnt[v + v + 1];
    sum[v] = sum[v + v] + sum[v + v + 1];

    pref_sums[v] = pref_sums[v + v] + pref_sums[v + v + 1];
    suf_sums[v] = suf_sums[v + v] + suf_sums[v + v + 1];
}

ll get_sum(int v, int tl, int tr, int l, int r){
    if (l > r) return ll(0);

    if (tl == l && tr == r) return sum[v];

    int md = (tl + tr) >> 1;

    return get_sum(v + v, tl, md, l, min(r, md)) +
            get_sum(v + v + 1, md + 1, tr, max(md + 1, l), r);
}

void pull(int v){
    cnt[v] = cnt[v + v] + cnt[v + v + 1];
    pref_sums[v] = pref_sums[v + v] + pref_sums[v + v + 1];
    suf_sums[v] = suf_sums[v + v] + suf_sums[v + v + 1];

    sum[v] = sum[v + v] + sum[v + v + 1];
}

void push_pref(int v){
    if (psh_pref[v] != 0){
        pref_sums[v] += cnt[v] * psh_pref[v];

        if (v + v + 1 < 4 * N){
            psh_pref[v + v] += psh_pref[v];
            psh_pref[v + v + 1] += psh_pref[v];
        }

        psh_pref[v] = 0;
    }
}

void upd_pref_sums(int v, int tl, int tr, int l, int r, ll vl){
    push_pref(v);

    if (l > r) return;

    if (tl == l && tr == r){
        psh_pref[v] += vl;
        push_pref(v);
        return;
    }

    int md = (tl + tr) >> 1;

    upd_pref_sums(v + v, tl, md, l, min(r, md), vl);
    upd_pref_sums(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    pref_sums[v] = pref_sums[v + v] + pref_sums[v + v + 1];
}




void push_suf(int v){
    if (psh_suf[v] != 0){
        suf_sums[v] += cnt[v] * psh_suf[v];

        if (v + v + 1 < 4 * N){
            psh_suf[v + v] += psh_suf[v];
            psh_suf[v + v + 1] += psh_suf[v];
        }

        psh_suf[v] = 0;
    }
}

void upd_suf_sums(int v, int tl, int tr, int l, int r, ll vl){
    push_suf(v);

    if (l > r) return;

    if (tl == l && tr == r){
        psh_suf[v] += vl;
        push_suf(v);
        return;
    }

    int md = (tl + tr) >> 1;

    upd_suf_sums(v + v, tl, md, l, min(r, md), vl);
    upd_suf_sums(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    suf_sums[v] = suf_sums[v + v] + suf_sums[v + v + 1];
}



void dobavaka(int v, int l, int r, int ps, ll npf, ll nsf){
    push_pref(v);
    push_suf(v);

    if (l == r){
        cnt[v] = 1;
        pref_sums[v] = npf;
        suf_sums[v] = nsf;
        sum[v] = elms[ps];

        psh_pref[v] = 0;
        psh_suf[v] = 0;

        return;
    }

    int md = (l + r) >> 1;

    push_pref(v + v);
    push_suf(v + v);

    push_pref(v + v + 1);
    push_suf(v + v + 1);

    if (ps <= md)
        dobavaka(v + v, l, md, ps, npf, nsf);
    else dobavaka(v + v + 1, md + 1, r, ps, npf, nsf);

    pull(v);
}

void ADD(ll x){
    int loc = lower_bound(all(elms), x) - elms.begin();

    ALL += x;

    ll nw_pref = get_sum(1, 0, sz(elms) - 1, 0, loc - 1) + x;
    ll nw_suf = ALL - nw_pref + x;

    dobavaka(1, 0, sz(elms) - 1, loc, nw_pref, nw_suf);

    /// change pref_sums && suf_sums

    upd_suf_sums(1, 0, sz(elms) - 1, 0, loc - 1, x);
    upd_pref_sums(1, 0, sz(elms) - 1, loc + 1, sz(elms) - 1, x);
}


void udalka(int v, int l, int r, int ps){
    push_pref(v);
    push_suf(v);

    if (l == r){
        cnt[v] = 0;
        pref_sums[v] = 0;
        suf_sums[v] = 0;
        sum[v] = 0;

        psh_pref[v] = 0;
        psh_suf[v] = 0;

        return;
    }

    int md = (l + r) >> 1;

    push_pref(v + v);
    push_suf(v + v);

    push_pref(v + v + 1);
    push_suf(v + v + 1);

    if (ps <= md)
        udalka(v + v, l, md, ps);
    else udalka(v + v + 1, md + 1, r, ps);

    pull(v);
}


void DEL(ll x){
    ALL -= x;

    int loc = lower_bound(all(elms), x) - elms.begin();

    udalka(1, 0, sz(elms) - 1, loc);

    upd_suf_sums(1, 0, sz(elms) - 1, 0, loc - 1, -x);
    upd_pref_sums(1, 0, sz(elms) - 1, loc + 1, sz(elms) - 1, -x);
}



int get_id(int v, int l, int r, ll need){
    if (l == r) return l;

    int md = (l + r) >> 1;

    if (cnt[v + v] < need)
        return get_id(v + v + 1, md + 1, r, need - cnt[v + v]);
    else return get_id(v + v, l, md, need);
}



ll get_pref_sums(int v, int tl, int tr, int l, int r){
    r = min(r, (int)cnt[1]);

    push_pref(v);

    if (l > r) return ll(0);

    if (l == 1 && cnt[v] == r) return pref_sums[v];

    int md = (tl + tr) >> 1;

    return get_pref_sums(v + v, tl, md, l, min(r, int(cnt[v + v]))) +
            get_pref_sums(v + v + 1, md, tr, max(1, l - int(cnt[v + v])), r - cnt[v + v]);
}

ll get_suf_sums(int v, int tl, int tr, int l, int r){
    r = min(r, (int)cnt[1]);

    push_suf(v);

    if (l > r) return ll(0);

    if (l == 1 && cnt[v] == r) return suf_sums[v];

    int md = (tl + tr) >> 1;

    return get_suf_sums(v + v, tl, md, l, min(r, int(cnt[v + v]))) +
            get_suf_sums(v + v + 1, md, tr, max(1, l - int(cnt[v + v])), r - cnt[v + v]);
}

void get_ans(){
    if (cnt[1] == 0){
        cout << "0\n";
        return;
    }

    int loc = (cnt[1] + 1) / 2;

    int id = get_id(1, 0, sz(elms) - 1, loc);

    ll ans = suf_sums[1];

//    cerr << get_pref_sums(1, 0, sz(elms) - 1, loc, loc) << '\n';
//    cerr << get_suf_sums(1, 0, sz(elms) - 1, cnt[1] - loc + 2, cnt[1] - loc + 2) << '\n';

    if (get_pref_sums(1, 0, sz(elms) - 1, loc, loc) <
            get_suf_sums(1, 0, sz(elms) - 1, cnt[1] - loc + 2, cnt[1] - loc + 2)){

        int l1 = 1, r1 = loc;

        while (l1 < r1){
            int md = (l1 + r1) >> 1;

            if (get_pref_sums(1, 0, sz(elms) - 1, md, md) <
                get_suf_sums(1, 0, sz(elms) - 1, cnt[1] - md + 2, cnt[1] - md + 2))
                    r1 = md;
                else l1 = md + 1;
        }

        int len = loc - l1 + 1;
        int l2 = loc + len;

        if (cnt[1] & 1) l2--;

        ans -= get_suf_sums(1, 0, sz(elms) - 1, cnt[1] - l2 + 2, cnt[1] - l1 + 2);

        ans -= get_pref_sums(1, 0, sz(elms) - 1, 1, l1 - 1);
        ans -= get_pref_sums(1, 0, sz(elms) - 1, l2 + 1, cnt[1]);

//        ans -= pref_sums[1];
//        ans += get_pref_sums(1, 0, sz(elms) - 1, l1, l2);
    } else {
        ans -= pref_sums[1];
    }

    cout << ans << '\n';
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> q;

    for (int i = 0; i < n; i++){
        cin >> a[i];
        elms.PB(a[i]);
    }

    for (int i = 1; i <= q; i++){
        cin >> TP[i] >> VL[i];

        if (TP[i] == 1)
            elms.PB(VL[i]);
    }

    sort(all(elms));
    elms.resize(unique(all(elms)) - elms.begin());

    for (int i = 0; i < n; i++){
        int cur = lower_bound(all(elms), a[i]) - elms.begin();

        INS[cur] = 1;

        se_glob += a[i];

        ALL += a[i];
    }

    build(1, 0, sz(elms) - 1);

//    for (int i = 0; i < n; i++){
//        /// add a[i] to seg_tree
//
//        ADD(a[i]);
//    }

    get_ans();

    for (int i = 1; i <= q; i++) {
        if (TP[i] == 1){
            ADD(VL[i]);
        } else {
            DEL(VL[i]);
        }

        get_ans();
    }

    return 0;
}
