#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) {
    cerr << a[i] << ' ';
  }
  cerr << endl;
}
#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif

const int logN = 19;
const int N = 1 << logN;
int n, Q;
ll rx[N], X;
bool S0[N];
int cx(ll x) {
  return lower_bound(rx, rx + X, x) - rx;
}

struct Query {
  int tp;
  ll x;
} qr[N / 2];

namespace sgt {
  struct Node {
    int cnt;
    ll sum;
    ll app; // 1 2 3 4 5 ... 
    ll apn; // ... 5 4 3 2 1
    
    Node(): cnt(0), sum(0), app(0), apn(0) {}
  } t[2 * N];

  Node operator * (const Node& lhs, const Node& rhs) {
    Node res;
    res.cnt = lhs.cnt + rhs.cnt;
    res.sum = lhs.sum + rhs.sum;
    res.app = lhs.app + rhs.app + rhs.sum * lhs.cnt;
    res.apn = lhs.apn + rhs.apn + lhs.sum * rhs.cnt;
    return res;
  }  

  void build() {
    for (int x = 0; x < X; ++x) {
      if (S0[x]) {
        t[x + N].cnt = 1;
        t[x + N].sum = t[x + N].app = t[x + N].apn = rx[x];
      }
    }
    for (int v = N - 1; v >= 1; --v) {
      t[v] = t[v << 1] * t[v << 1 | 1];
    }
  }

  void flip(int i) {
    int v = i + N;
    if (t[v].cnt == 0) {
      t[v].cnt = 1;
      t[v].sum = t[v].app = t[v].apn = rx[i];
    } else {
      t[v].cnt = t[v].sum = t[v].app = t[v].apn = 0;
    }
    for (v >>= 1; v >= 1; v >>= 1) {
      t[v] = t[v << 1] * t[v << 1 | 1];
    }
  }

  int _get_kth(int v, int vl, int vr, int k) {
    if (vl == vr) {
      return vl;
    }
    int vm = (vl + vr) >> 1;
    if (t[v << 1].cnt > k) {
      return _get_kth(v << 1, vl, vm, k);
    } else {
      return _get_kth(v << 1 | 1, vm + 1, vr, k - t[v << 1].cnt);
    }
  }

  int get_kth(int k) {
    return _get_kth(1, 0, N - 1, k - 1);
  }

  Node gt(int l, int r) {
    Node lv, rv;
    for (l += N, r += N; l <= r; l >>= 1, r >>= 1) {
      if (l & 1)  lv = lv * t[l++];
      if (~r & 1) rv = t[r--] * rv;
    }
    return lv * rv;
  }

  ll _sum_first_k(int v, int vl, int vr, int k) {
    if (!k) {
      return 0;
    }
    if (vl == vr) {
      return t[v].sum;
    }
    int vm = (vl + vr) >> 1;
    if (t[v << 1].cnt >= k) {
      return _sum_first_k(v << 1, vl, vm, k);
    } else {
      return t[v << 1].sum + _sum_first_k(v << 1 | 1, vm + 1, vr, k - t[v << 1].cnt);
    }
  }

  ll sum_first_k(int k) {
    return _sum_first_k(1, 0, N - 1, k);
  }

  ll _sum_last_k(int v, int vl, int vr, int k) {
    if (!k) {
      return 0;
    }
    if (vl == vr) {
      return t[v].sum;
    }
    int vm = (vl + vr) >> 1;
    if (t[v << 1 | 1].cnt >= k) {
      return _sum_last_k(v << 1 | 1, vm + 1, vr, k);
    } else {
      return t[v << 1 | 1].sum + _sum_last_k(v << 1, vl, vm, k - t[v << 1 | 1].cnt);
    }
  }

  ll sum_last_k(int k) {
    return _sum_last_k(1, 0, N - 1, k);
  }
}

ll diff(int k) { // R[k] >= L[k + 1]
  return sgt::sum_last_k(k) - sgt::sum_first_k(k + 1);
}

ll sum_seg_len(int l, int r) {
  int len = r - l + 1;
  if (len <= 0) {
    return 0;
  }
  ll ans = 0;
  {
    int il = sgt::get_kth(l);
    int ir = sgt::get_kth(r);
    auto pref = sgt::gt(0, il - 1);
    auto segm = sgt::gt(il, ir);
    ans -= (pref.sum * len + segm.apn);
  }
  {
    int il = sgt::get_kth(n - (l - 1));
    int ir = sgt::get_kth(n - (r - 1));
    auto suf  = sgt::gt(il + 1, X);
    auto segm = sgt::gt(ir, il);
    ans += suf.sum * len + segm.app;
  }
  return ans;
}

ll rec() {
  /*cerr << endl << endl;
  debug(n);
  for (int i = 1; i <= n; ++i) {
    cerr << sgt::get_kth(i) << ' ';
  }
  cerr << endl;
  for (int k = 1; k <= n - 1; ++k) {
    cerr << "[" << sgt::sum_first_k(k) << ' ' << sgt::sum_last_k(k) << ")   ";
  }
  cerr << endl;/**/
  if (n == 1) {
    return 0;
  }
  if (diff((n + 1) / 2 - 1) < 0) {
    return sum_seg_len(1, n - 1);
  }
  int L, R;
  {
    int vl = 0;
    int vr = (n + 1) / 2 - 1;
    while (vr - vl > 1) {
      int vm = (vl + vr) >> 1;
      if (diff(vm) >= 0) {
        vr = vm;
      } else {
        vl = vm;
      }
    }
    L = vr;
  }
  {
    int vl = (n + 1) / 2 - 1;
    int vr = n - 1;
    while (vr - vl > 1) {
      int vm = (vl + vr) >> 1;
      if (diff(vm) >= 0) {
        vl = vm;
      } else {
        vr = vm;
      }
    }
    R = vl + 1;
  }
  /*debug(L, R);
  debug(sgt::sum_first_k(L));
  debug(sgt::sum_last_k(R));/**/
  return sum_seg_len(1, L - 1) + sum_seg_len(R + 1, n - 1) + sgt::sum_last_k(R) - sgt::sum_first_k(L);
}

int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> Q;
  vector<ll> a0(n);
  for (auto& x : a0) {
    cin >> x;
    rx[X++] = x;
  }
  for (int qi = 0; qi < Q; ++qi) {
    auto &q = qr[qi];
    cin >> q.tp >> q.x;
    rx[X++] = q.x;
  }
  sort(rx, rx + X);
  X = unique(rx, rx + X) - rx;
  for (ll& x : a0) {
    S0[cx(x)] = true;
  }
  //mdebug(rx, X);
  //mdebug(S0, X);
  sgt::build();
  cout << rec() << '\n';
  for (int qi = 0; qi < Q; ++qi) {
    auto &q = qr[qi];
    if (q.tp == 1) {
      ++n;
    } else {
      --n;
    }
    sgt::flip(cx(q.x));
    cout << rec() << '\n';
  }

  return 0;
}
