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

const int N = 4e5+10;
// root 表示整棵线段树的根结点；cnt 表示当前结点个数
int n, cnt, root;
int sum[N * 2], num[N * 2], ls[N * 2], rs[N * 2];

// 用法：update(root, 1, n, x, f); 其中 x 为待修改节点的编号
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]];  // pushup
	num[p] = num[ls[p]] + num[rs[p]];
}

// 用法：query(root, 1, n, l, r);
int query1(int p, int s, int t, int l, int r)
{
	if (!p) return 0;  // 如果结点为空，返回 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;  // 如果结点为空，返回 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];

void solve()
{
	int n, q;
	cin >> n >> q;
	int R = 1000000000, 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 l = 1, r = R;
		while (l < r)
		{
			int mid = (l + r) >> 1;
			if (query1(root, 1, R, 1, mid) + summ > 0)
				r = mid;
			else
				l = mid + 1;
		}
		int minn = query2(root, 1, R, l, R);
		cout << maxx - minn + 1 << '\n';
	}
}

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