#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define rep(i,a,b) for(auto i = (a); i != (b); ++i)
#define REP(i,n) rep(i,0,n)
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int maxn = 1e5 + 350, sqrtmaxn = 350;

int N, nbins, binsize;
// sum, binsum,          cumulative sum in bin
ll A[maxn] = {}, BS[sqrtmaxn] = {}, CS[sqrtmaxn][sqrtmaxn] = {};

ll F(int idx)
{
	int q = idx / binsize, r = idx % binsize;
	return BS[nbins] - A[idx] - 2LL * (BS[q] + CS[q][r]);
}

ll SF(int idx)
{
	ll ret = abs(F(idx));
	if (A[idx] % 2LL == 0LL)
		return ret;

	if (ret == 0LL) return 1LL;
	return ret - 1LL;
}

int hut_pos()
{
	// find bin first.

	/*
	cout << "SUM: " << BS[nbins] << endl;
	REP(i, N) cout << A[i] << " ";
	cout << endl;
	REP(i, nbins) cout << BS[i] << " ";
	cout << ", ";

	for (int i = 0; i < N; i++) {
		cout << i << ": " << F(i) << endl;
	}
	*/

	int lo = -1, hi = N - 1;
	while (hi - lo > 1) {
		int mi = (lo + hi) / 2;
		if (F(mi) >= 0LL) lo=mi;
		else hi=mi;
	}

	if (lo < 0) return 0;
	if (hi >= N) hi = lo--;

	ll flo = SF(lo), fhi = SF(hi);

	ll bestVal = min(flo, fhi);
	int best = flo <= fhi ? lo : hi;

	if (lo > 0) {
		ll alt = SF(lo - 1);
		if (alt <= bestVal)
			bestVal = alt, best = lo - 1;
	}
	return best;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
//	cout.tie(NULL);

	int Q;
	cin >> N >> Q;
	REP(i, N) cin >> A[i];

	binsize = sqrt(N);
	nbins = N / binsize;
	if (N % binsize != 0) {
		N += binsize - (N % binsize);
		nbins++;
	}

	// cerr << "Setting N = " << N << " = " << nbins << " x " << binsize << endl;

	// sum over bins
	REP(i, nbins) CS[i][0] = 0LL;

	REP(i, nbins) REP(j, binsize)
		CS[i][j + 1] = CS[i][j] + A[i * binsize + j];
	REP(i, nbins)
		BS[i + 1] = BS[i] + CS[i][binsize];

	vi ret(Q);
	REP(i, Q) { 
		int p, q, v;
		cin >> p >> v;
		q = p / binsize;

		// delta:
		ll inc = v - A[p];

		// update sums in O(√N):
		for (int r = p % binsize; ++r < binsize; ) CS[q][r] += inc;
		for (int r = q; ++r <= nbins; ) BS[r] += inc;

		// update value
		A[p] = v;

//		if (i == 24) {
//			cerr << "QUERY : " << p << " " << q << " " << v << endl;
//			REP(j, N) cerr << A[j] << " ";
//			cerr << endl;
//		}

		ret[i] = hut_pos();
	}

	REP(i, Q) printf("%d\n", ret[i]);
	return 0;
}