#include <cstdio>
#include <cstdlib>
#include <unordered_map>
using namespace std;

const int MAXN = 2e5 + 10;
const int INF = 0x7fffffff;

struct NODE {
	int ls, rs;
	int cnt, num, numin;
	int qwq;
} node[MAXN];
int root, nodeNum;

int New(int cnt, int num) {
	node[++nodeNum].cnt = cnt;
	node[nodeNum].num = num;
	node[nodeNum].numin = num;
	node[nodeNum].qwq = rand();
	return nodeNum;
}

void Build(int &root) {
	root = New(-INF, -INF);
	node[root].rs = New(INF, INF);
	return ;
}

void zig(int &root) {
	int lson = node[root].ls;
	node[root].ls = node[lson].rs;
	node[lson].rs = root;
	root = lson;
}

void zag(int &root) {
	int rson = node[root].rs;
	node[root].rs = node[rson].ls;
	node[rson].ls = root;
	root = rson;
}

void Insert(int &root, int cnt, int num) {
	if (node[root].cnt == cnt) {
		if (num > node[root].num) {
			node[root].num = num;
		}
		if (num < node[root].numin) {
			node[root].numin = num;
		}
		return ;
	}
	if (!root) {
		root = New(cnt, num);
		return ;
	}
	if (cnt < node[root].cnt) {
		Insert(node[root].ls, cnt, num);
		if (node[node[root].ls].qwq > node[root].qwq) zig(root);
	} else {
		Insert(node[root].rs, cnt, num);
		if (node[node[root].rs].qwq > node[root].qwq) zag(root);
	}
}

void Remove(int &root, int cnt, int num) {
	if (node[root].cnt == cnt) {
		if (node[root].num != num) return ;
		if (node[root].ls || node[root].rs) {
			if (!node[root].rs || node[node[root].rs].qwq < node[node[root].ls].qwq) {
				zig(root);
				Remove(node[root].rs, cnt, num);
			} else {
				zag(root);
				Remove(node[root].ls, cnt, num);
			}
		} else {
			root = 0;
		}
		return ;
	}
	if (cnt < node[root].cnt) Remove(node[root].ls, cnt, num);
	else Remove(node[root].rs, cnt, num);
}

int GetMax(int root) {
	if (node[root].cnt == INF) root = node[root].ls;
	while (node[root].rs && node[node[root].rs].cnt != INF) root = node[root].rs;
	return node[root].num;
}

int GetMin(int root) {
	if (node[root].cnt == -INF) root = node[root].rs;
	while (node[root].ls && node[node[root].ls].cnt != -INF) root = node[root].ls;
	return node[root].numin;
}

int n, q;
int a[MAXN];
unordered_map <int, int> cnts;

int main() {
	freopen("Queries.in", "r", stdin);
	freopen("Queries.out", "w", stdout);
	Build(root);
	scanf("%d %d", &n, &q);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		cnts[a[i]]++;
	}
	for (auto x : cnts) {
		Insert(root, x.second, x.first);
	}
	while (q--) {
		int i, x;
		scanf("%d %d", &i, &x);
		Remove(root, cnts[a[i]], a[i]);
		cnts[a[i]]--;
		a[i] = x;
		cnts[a[i]]++;
		Insert(root, cnts[a[i]], a[i]);
		printf("%d\n", abs(GetMax(root) - GetMin(root)));
	}
	return 0;
}