#include<bits/stdc++.h>

#define ll long long
using namespace std;

inline int qr() {
    int f = 0, fu = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')fu = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        f = (f << 3) + (f << 1) + (c & 15);
        c = getchar();
    }
    return f * fu;
}

const int N = 2e5 + 10;

struct Seg_Tree {
    struct {
        int l, r, num;
        ll sum, sL, sR;
    } t[N << 3];

#define update(p) {                                                                   \
        t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;                                 \
        t[p].num = t[p << 1].num + t[p << 1 | 1].num;                                 \
        t[p].sL = t[p << 1].sL + t[p << 1].sum * t[p << 1 | 1].num + t[p << 1 | 1].sL;\
        t[p].sR = t[p << 1].sR + t[p << 1 | 1].sum * t[p << 1].num + t[p << 1 | 1].sR;\
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r)
            return t[p].sum = t[p].sL = t[p].sR = t[p].num = 0, void();
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        update(p);
    }

    void change(int p, int x, ll v) {
        if (t[p].l == t[p].r) {
            t[p].sum += v, t[p].sL += v, t[p].sR += v;
            t[p].num += v < 0 ? -1 : 1;
            return;
        }
        int mid = (t[p].l + t[p].r) >> 1;
        change(x <= mid ? p << 1 : p << 1 | 1, x, v);
        update(p);
    }

    ll ask_L(int p, int x) {
        if (t[p].num <= x)return t[p].sum;
        ll val = ask_L(p << 1, x);
        if (x > t[p << 1].num)
            val += ask_L(p << 1 | 1, x - t[p << 1].num);
        return val;
    }

    ll ask_R(int p, int x) {
        if (t[p].num <= x)return t[p].sum;
        ll val = ask_R(p << 1 | 1, x);
        if (x > t[p << 1 | 1].num)
            val += ask_R(p << 1, x - t[p << 1 | 1].num);
        return val;
    }

    ll ask_sL(int p, int x) {
        if (t[p].num <= x)return t[p].sL;
        ll val = ask_sL(p << 1, x);
        if (x > t[p << 1].num)
            val += t[p << 1].sum * (x - t[p << 1].num) + ask_sL(p << 1 | 1, x - t[p << 1].num);
        return val;
    }

    ll ask_sR(int p, int x) {
        if (t[p].num <= x)return t[p].sR;
        ll val = ask_sR(p << 1 | 1, x);
        if (x > t[p << 1 | 1].num)
            val += t[p << 1 | 1].sum * (x - t[p << 1 | 1].num) + ask_sR(p << 1, x - t[p << 1 | 1].num);
        return val;
    }
} S;

int n, q;
ll a[N];
vector<ll> v;
pair<int, ll> p[N];
#define f(x) (S.ask_R(1, x)-S.ask_L(1,x+1))

inline ll solve() {
    if (n <= 1)return 0ll;
    int l = 1, r = n, lmid, rmid, pmx;
    ll fl,fr;
    while (l <= r) {
        lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        fl = f(lmid), fr = f(rmid);
        if(fl>0){pmx=lmid;break;}
        if(fr>0){pmx=rmid;break;}
        f(lmid) <= f(rmid) ? (l = lmid + 1, pmx = rmid) : (r = rmid - 1);
    }
    if (f(pmx) <= 0)return S.t[1].sR - S.t[1].sL;
    int pl = 1, pr = n - 1;
    if (f(pl) < 0) {
        l = 1, r = pmx;
        while (l < r) {
            int mid = (l + r) >> 1;
            f(mid) >= 0 ? (r = mid) : (l = mid + 1);
        }
        pl = l;
    }
    if (f(pr - 1) < 0) {
        l = pmx, r = n - 2;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            f(mid) >= 0 ? (l = mid) : (r = mid - 1);
        }
        pr = l + 1;
    }
    ll ans = S.ask_R(1, pr) - S.ask_L(1, pl);
    if (pl > 1)ans += S.ask_sR(1, pl - 1) - S.ask_sL(1, pl - 1);
    if (pr < n - 1)ans += (S.t[1].sR - S.ask_sR(1, pr)) - (S.t[1].sL - S.ask_sL(1, pr));
    return ans;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), v.push_back(a[i]);
    for (int i = 1; i <= q; i++) {
        scanf("%d%lld", &p[i].first, &p[i].second);
        v.push_back(p[i].second);
    }
    v.push_back(0);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    for (int i = 1; i <= q; i++)
        p[i].second = lower_bound(v.begin(), v.end(), p[i].second) - v.begin();
    S.build(1, 1, (int) v.size() - 1);
    for (int i = 1; i <= n; i++)S.change(1, a[i], v[a[i]]);
    printf("%lld\n", solve());
    for (int i = 1; i <= q; i++) {
        if (p[i].first == 1) {
            n++;
            S.change(1, p[i].second, v[p[i].second]);
        } else {
            n--;
            S.change(1, p[i].second, -v[p[i].second]);
        }
        printf("%lld\n", solve());
    }
    return 0;
}