#include<bits/stdc++.h>

#define ll long long
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)

using namespace std;

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 2e5 + 5;

int n, m, a[N];
ll cnt, sum;

namespace sgt {
	ll tre[N << 2], ad[N << 2];
	#define mid (l + r >> 1)
	#define ls (k << 1)
	#define rs (k << 1 | 1)
	inline void ps(int k, ll v) { tre[k] += v; ad[k] += v; }
	inline void psd(int k) { if(ad[k]) ps(ls, ad[k]), ps(rs, ad[k]); ad[k] = 0; }
	inline void psu(int k) { tre[k] = max(tre[ls], tre[rs]); }
	inline void modify(int k, int l, int r, int L, int R, ll v) {
		if(!v || L > R || L > r || R < l) return ;
		if(L <= l && R >= r) return ps(k, v); psd(k);
		modify(ls, l, mid, L, R, v); modify(rs, mid + 1, r, L, R, v); psu(k);
	}
}
using namespace sgt;

inline void update(int x, int v) {
	if(a[x] & 1) modify(1, 1, n, 1, x, -1), --cnt;
	modify(1, 1, n, 1, 2 * x - 1, a[x] / 2), sum -= a[x] / 2;
	a[x] += v;
	if(a[x] & 1) modify(1, 1, n, 1, x, 1), ++cnt;
	modify(1, 1, n, 1, 2 * x - 1, - (a[x] / 2)), sum += a[x] / 2;
}

signed main() {
	n = read(); m = read();
	rep(i, 1, n) update(i, read());
	
	for(int i = 1, u, v; i <= m; i++) {
		u = read(), v = read(); update(u, v); 
		ll ans = cnt - max(0ll, tre[1]); 
		ans += (sum - ans) * 2 / 3;
		printf("%lld\n", ans);
	}
	return 0;
}