// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstdio>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;

#define PB push_back
#define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) { rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1]; }

const int N = 2e5;
int a, b, s[N + 5], sum, w[N * 4 + 5], val[N + 5], mx[N * 4 + 5], tmp;

// int get(int n, int l, int r, int k) {
// 	if(k >= mx[n]) return mx[n];
// 	if(l == r) return k;
// 	int mid = (l + r) >> 1;
// 	if(k >= mx[rs]) return get(ls, l, mid, k - mx[rs]) + mx[rs];
// 	return get(rs, mid + 1, r, k);
// }
#define ls n << 1
#define rs n << 1 | 1
void add(int n, int l, int r, int k, int p) {
	if(l == r) {
		val[l] += p;
		w[n] = max(0ll, val[l]);
		mx[n] = max(0ll, -val[l]);
		return;
	}
	int mid = (l + r) >> 1;
	if(k <= mid) add(ls, l, mid, k, p);
	else add(rs, mid + 1, r, k, p);
	mx[n] = max(mx[rs], mx[ls] - w[rs]);
	w[n] = max(0ll, w[rs] - mx[ls]) + w[ls];
}
void ins(int n, int m) {
	sum += m;
	if(s[n] & 1) add(1, 1, a, n, 1), ++sum;
	tmp -= s[n] / 2;
	add(1, 1, a, min(a, 2 * n - 1), -s[n] / 2);
	s[n] += m;
	if(s[n] & 1) add(1, 1, a, n, -1), --sum;
	add(1, 1, a, min(a, 2 * n - 1), s[n] / 2);
	tmp += s[n] / 2;
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> a >> b;
	int x, y;
	rep(i, 1, a) cin >> x, ins(i, x);
	rep(i, 1, b) {
		cin >> x >> y;
		ins(x, y);
		// cout << tmp << ' ' << w[1] << endl;
		// rep(i, 1, a) cout << val[i] << " \n"[i == a];
		cout << (sum + tmp - w[1]) / 3 << '\n';
	}
	return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}