#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define INF 0x3f3f3f3f
#define INFLL (long long)(1e18)
#define EPS 1e-9

#ifndef LOCAL
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target(                                                            \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("section-anchors")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#endif

#define FORCE_INLINE inline __attribute__((always_inline))

template <class T> istream& operator>>(istream& is, vector<T>& a) {
    for (size_t i = 0; i < a.size(); ++i)
        is >> a[i];
    return is;
}

#define int long long
#define ll long long

#ifndef LOCAL
mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#else
mt19937_64 gen(239);
#endif

struct Node {
    int x, y, sz;
    ll sum, sumind;
    int add;
    Node* l, * r;

    Node() {};
    Node(int a)
        : x(a), y(gen()), sz(1), sum(x), sumind(x), add(0), l(0), r(0) {};
};

int get_size(Node* root) {
    return (root != nullptr ? root->sz : 0);
}

void upd_size(Node*& root) {
    if (root != nullptr)
        root->sz = get_size(root->l) + get_size(root->r) + 1;
}

int get_sum(Node* root) {
    return (root != nullptr ? root->sum : 0);
}

void upd_sum(Node*& root) {
    if (root != nullptr)
        root->sum = get_sum(root->l) + get_sum(root->r) + root->x;
}

ll get_sumind(Node* root) {
    return (root != nullptr ? root->sumind : 0);
}

void upd_sumind(Node*& root) {
    if (root != nullptr)
        root->sumind = get_sumind(root->l) +
        root->x * ((ll)get_size(root->l) + 1) +
        get_sumind(root->r) +
        get_sum(root->r) * ((ll)get_size(root->l) + 1);
}

void update(Node*& root) {
    upd_size(root);
    upd_sum(root);
    upd_sumind(root);
}

void merge(Node*& root, Node* l, Node* r) {
    if (l == nullptr || r == nullptr)
        root = (l != nullptr) ? l : r;
    else if (l->y > r->y)
        merge(l->r, l->r, r), root = l;
    else
        merge(r->l, l, r->l), root = r;
    update(root);
}

void split_key(Node* t, Node*& l, Node*& r, int key, int add = 0) {
    if (t == nullptr) {
        l = r = nullptr;
        return;
    }
    int cur_key = add + get_size(t->l);
    if (key <= cur_key)
        split_key(t->l, l, t->l, key, add), r = t;
    else
        split_key(t->r, t->r, r, key, add + 1 + get_size(t->l)), l = t;
    update(t);
    // update(l);
    // update(r);
}

void split_val(Node* t, Node*& l, Node*& r, int val) {
    if (t == nullptr) {
        l = r = nullptr;
        return;
    }
    if (val < t->x)
        split_val(t->l, l, t->l, val), r = t;
    else
        split_val(t->r, t->r, r, val), l = t;
    update(t);
    // update(l);
    // update(r);
}

void insert(Node*& root, int val) {

    Node* l, * r;
    split_val(root, l, r, val);
    Node* new_item = new Node(val);
    merge(l, l, new_item);
    merge(root, l, r);

}

void insert(Node*& root, Node* v) {
    if (root == nullptr || v->y > root->y)
    {
        split_val(root, v->l, v->r, v->x);
        update(v);
        root = v;
        return;
    }
    if (v->x < root->x)
        insert(root->l, v);
    else
        insert(root->r, v);
    update(root);
}


void erase(Node*& root, int val) {
    
    Node* l1, * r1, * l2, * r2;
    split_val(root, l1, r1, val);
    split_val(l1, l2, r2, val - 1);
    merge(root, l2, r1);
    
}

Node* root = nullptr;

/*
ll max(ll a, ll b) {
    return (a > b) ? a : b;
}
*/

void print(Node* t) {
    if (t == nullptr)
        return;
    print(t->l);
    cout << t->x << "\n";
    print(t->r);
}

/*
ostream &operator<<(ostream &os, ll a) {
    string ans;
    if (a < 0) {
        os << '-';
        a *= -1;
    }
    if (a == 0) {
        os << 0;
        return os;
    }
    while (a > 0) {
        ans.push_back(a % 10 + '0');
        a /= 10;
    }
    reverse(all(ans));
    os << ans;
    return os;
}
*/

long long sum_prefix(Node* root, int k)
{
    if (root == nullptr) return 0;
    if (k <= 0) return 0;
    if (get_size(root) <= k) return root->sum;
    long long ans = 0;
    if (k > get_size(root->l)) ans += root->x;
    ans += sum_prefix(root->l, k) +
        sum_prefix(root->r, k - get_size(root->l) - 1);
    return ans;
}


ll solve() {
    int n = get_size(root);
    int l = 0, r = n / 2;
    while (l + 1 < r) {
        int k = (l + r) / 2;
        Node* l1, * r1;

        //
        int sum_left = sum_prefix(root, k + 1);
        int sum_right = get_sum(root) - sum_prefix(root, n - k);


        /*
        split_key(root, l1, r1, k + 1);
        int sum_left = get_sum(l1);
        merge(root, l1, r1);
        Node* l2, * r2;
        split_key(root, l2, r2, n - k);
        int sum_right = get_sum(r2);
        merge(root, l2, r2);
        */
        if (sum_left > sum_right)
            l = k;
        else
            r = k;
    }
    // cout << "!!!\n" << l << "\n!!!\n";
    ll ans = 0, odd = 0;
    if (n % 2 != 0 && l >= n / 2 - 1) {

        Node* l1, * r1;
        split_key(root, l1, r1, n / 2 + 1);
        ll sum_left = get_sum(l1);
        merge(root, l1, r1);
        ll sum_right = get_sum(root) - sum_left;
        /*
        Node* l1, * r1;
        split_key(root, l1, r1, n / 2 + 1);
        ll sum_left = get_sum(l1);
        merge(root, l1, r1);
        Node* l2, * r2;
        split_key(root, l2, r2, n - n / 2);
        ll sum_right = get_sum(r2);
        merge(root, l2, r2);
        */
        if (sum_left > sum_right)
            odd = sum_left - sum_right;
    }
    // print(root);

    Node* l1, * r1;
    Node* l2, * r2;
    split_key(root, l2, r2, n - l);
    ans -= get_sumind(r2);

    split_key(l2, l1, r1, l + 1);
    ans += (get_size(l1) + 1) * get_sum(l1) - get_sumind(l1);
    merge(l2, l1, r1);
    merge(root, l2, r2);

    /*
    Node* l1, * r1;
    split_key(root, l1, r1, l + 1);
    ans += (get_size(l1) + 1) * get_sum(l1) - get_sumind(l1);
    merge(root, l1, r1);
    Node* l2, * r2;
    split_key(root, l2, r2, n - l);
    ans -= get_sumind(r2);
    merge(root, l2, r2);
    */
    // cout << get_sum(root) << " " << ans << "\n";
    return max((ll)0, get_sum(root) - ans * 2 - odd);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // cout << gen() << endl;
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        insert(root, x);
    }
    // print(root);
    cout << solve() << "\n";
    // print(root);
    while (q--) {
        int t, a;
        cin >> t >> a;
        if (t == 1)
    //    {
      //      Node* v = new Node(a);
        //    insert(root, v);
        //}
           insert(root, a);
        else {
            erase(root, a);
            //        cout << "\n";
              //      print(root);
                //    cout << "\n";
        }
        cout << solve() << "\n";
    }
}
