#include<bits/stdc++.h>
using namespace std;typedef long long llint;typedef pair <llint, llint> pi;const int MAXN = 400005;
int n, q, ofs = 1;llint s[MAXN], tip[MAXN], a[MAXN];llint br[MAXN * 4], sum[MAXN * 4], upp[MAXN * 4], dwn[MAXN * 4];vector <llint> saz;
void spoji (int a, int b, int c) {  br[c] = br[a] + br[b];   sum[c] = sum[a] + sum[b];   upp[c] = upp[a] + upp[b] + sum[b] * br[a];   dwn[c] = dwn[a] + dwn[b] + sum[a] * br[b];}
void tour_init () {while (ofs < saz.size()) ofs *= 2; for (int i = 1; i <= n; i++) {
        int pos = lower_bound(saz.begin(), saz.end(), s[i]) - saz.begin();  br[pos + ofs] = 1; sum[pos + ofs] = upp[pos + ofs] = dwn[pos + ofs] = s[i]; }
    for (int i = ofs - 1; i > 0; i--)   spoji(2 * i, 2 * i + 1, i);}
void update (int pos, llint val) { pos += ofs;  if (br[pos]) {    br[pos] = sum[pos] = upp[pos] = dwn[pos] = 0;
    } else {   br[pos] = 1;   sum[pos] = upp[pos] = dwn[pos] = val;  }  pos /= 2; while (pos > 0) {   spoji(pos * 2, pos * 2 + 1, pos);   pos /= 2;  }}
llint pref_sum (int x, int k) { if (k == br[x]) return sum[x]; if (k <= br[2 * x]) return pref_sum(2 * x, k); return sum[2 * x] + pref_sum(2 * x + 1, k - br[2 * x]);}
llint suf_sum (int x, int k) { if (k == br[x]) return sum[x];  if (k <= br[2 * x + 1]) return suf_sum(2 * x + 1, k); return sum[2 * x + 1] + suf_sum(2 * x, k - br[2 * x + 1]);}
llint pref_dwn (int x, int k) {  if (k == br[x]) return dwn[x];  if (k <= br[2 * x]) return pref_dwn(2 * x, k);  return dwn[2 * x] + sum[2 * x] * (k - br[2 * x]) + pref_dwn(2 * x + 1, k - br[2 * x]);}
llint suf_upp (int x, int k) {  if (k == br[x]) return upp[x];  if (k <= br[2 * x + 1]) return suf_upp(2 * x + 1, k);  return upp[2 * x + 1] + sum[2 * x + 1] * (k - br[2 * x + 1]) + suf_upp(2 * x, k - br[2 * x + 1]);}
llint calc () {  if (br[1] == 0) return 0;  int lo = 1, hi = (br[1] + 1) / 2;  while (lo < hi) {   int mid = (lo + hi + 1) / 2;   llint pref = pref_sum(1, mid);
        llint suf = suf_sum(1, mid - 1);   if (pref - suf > 0) {   lo = mid;    } else {     hi = mid - 1;  } }
    int k = lo;    llint sol = 0;  if (k - 1 > 0)   sol += 2 * (suf_upp(1, k - 1) - pref_dwn(1, k - 1));
    if (k * 2 != br[1] + 1) sol += suf_sum(1, br[1] - k) - pref_sum(1, k);   return sol;}
int main () {  ios_base::sync_with_stdio(false); cin.tie(0);  cin >> n >> q;  for (int i = 1; i <= n; i++) {    cin >> s[i];    saz.push_back(s[i]);  }
    for (int i = 1; i <= q; i++) {  cin >> tip[i] >> a[i];    saz.push_back(a[i]); }    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());  tour_init();  cout << calc() << endl;
    for (int i = 1; i <= q; i++) {  int pos = lower_bound(saz.begin(), saz.end(), a[i]) - saz.begin();   update(pos, a[i]);    cout << calc() << endl;}    return 0;}