/*
doing virtual contest
start: 10:00
finish: 14:00
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int n = (int)a.size(), q = (int)x.size();
vector<int> all;
for (int i = 0; i < n; ++i) all.push_back(a[i]);
for (int i = 0; i < q; ++i) all.push_back(v[i]);
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
for (int i = 0; i < n; ++i) a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
for (int i = 0; i < q; ++i) v[i] = lower_bound(all.begin(), all.end(), v[i]) - all.begin();
vector<set<int>> st((int)all.size());
for (int i = 0; i < n; ++i) st[a[i]].insert(i);
vector<int> s;
for (int j = 0; j < q; ++j) {
st[a[x[j]]].erase(x[j]);
a[x[j]] = v[j];
st[v[j]].insert(x[j]);
int cnt = 0, ans = 0;
for (int i = 0; i < (int)all.size(); ++i) {
if (!st[i].empty()) ans = max(ans, *st[i].rbegin() - cnt - (int)st[i].size() + 1);
cnt += (int)st[i].size();
}
s.push_back(ans);
}
return s;
}
#ifdef LOCAL
int main() {
freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> x(q), v(q);
for (int i = 0; i < q; ++i) cin >> x[i] >> v[i];
auto s = countScans(a, x, v);
for (int i = 0; i < q; ++i) cout << s[i] << '\n';
return 0;
}
#endif
