#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 4e5+10, R = 1000000000;
int n, cnt, root;
int sum[N * 2], num[N * 2], ls[N * 2], rs[N * 2];

void update(int& p, int s, int t, int x, int f)
{
	if (!p) p = ++cnt;
	if (s == t)
	{
		sum[p] += x*f;
		num[p] += f;
		return;
	}
	int m = s + ((t - s) >> 1);
	if (x <= m)
		update(ls[p], s, m, x, f);
	else
		update(rs[p], m + 1, t, x, f);
	sum[p] = sum[ls[p]] + sum[rs[p]];
	num[p] = num[ls[p]] + num[rs[p]];
}

int query1(int p, int s, int t, int l, int r)
{
	if (!p) return 0;
	if (s >= l && t <= r) return sum[p];
	int m = s + ((t - s) >> 1), ans = 0;
	if (l <= m) ans += query1(ls[p], s, m, l, r);
	if (r > m) ans += query1(rs[p], m + 1, t, l, r);
	return ans;
}

int query2(int p, int s, int t, int l, int r)
{
	if (!p) return 0;
	if (s >= l && t <= r) return num[p];
	int m = s + ((t - s) >> 1), ans = 0;
	if (l <= m) ans += query2(ls[p], s, m, l, r);
	if (r > m) ans += query2(rs[p], m + 1, t, l, r);
	return ans;
}

int a[N];

int getminn(int summ)
{
	int l = 1, r = R;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (query1(root, 1, R, 1, mid) > summ)
			r = mid;
		else
			l = mid + 1;
	}
	int minn = query2(root, 1, R, l, R);
	int summm = l > 1 ? query1(root, 1, R, 1, l - 1) : 0;
	int c = summ - summm;
	int numm = c / l +1;
	minn -= numm - 1;
	return minn;
}

void solve()
{
	int n, q;
	cin >> n >> q;
	int summ = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		update(root, 1, R, a[i], 1);
		if (a[i] < 0)summ += a[i];
	}
	while (q--)
	{
		int x, v;
		cin >> x >> v;
		if (a[x] > 0)
			update(root, 1, R, a[x], -1);
		if (v > 0)
			update(root, 1, R, v, 1);
		if (a[x] < 0)summ -= a[x];
		if (v < 0)summ += v;
		a[x] = v;
		int maxx = query2(root, 1, R, 1, R);
		int minn = getminn(-summ);
		cout << maxx - minn + 1 << '\n';
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}