#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
template<typename T>
bool minimize(T& a, const T& b){
if(a > b){
return a = b, true;
}
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b){
return a = b, true;
}
return false;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
const int inf = 1e9;
struct segment_tree{
vector<int> sum, st, lazy;
segment_tree(int n) : sum(n << 2), st(n << 2, -inf), lazy(n << 2) {}
void apply(int id, int val){
st[id] += val;
sum[id] += val;
lazy[id] += val;
}
void down(int id){
if(lazy[id] != 0){
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
}
void add(int id, int l, int r, int u, int v, int val){
if(u <= l && r <= v) apply(id, val);
else{
int mid = l + r >> 1;
down(id);
if(u <= mid) add(id << 1, l, mid, u, v, val);
if(mid < v) add(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
void change(int id, int l, int r, int pos, int val){
if(l == r) st[id] = val + sum[id];
else{
int mid = l + r >> 1;
down(id);
if(pos <= mid) change(id << 1, l, mid, pos, val);
else change(id << 1 | 1, mid + 1, r, pos, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
void debug(int id, int l, int r){
if(l == r) cout << dbg(l) << dbg(st[id]) << '\n';
else{
int mid = l + r >> 1;
debug(id << 1, l, mid);
debug(id << 1 | 1, mid + 1, r);
}
}
int query(){ return st[1]; }
};
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int N = sz(A);
int Q = sz(X);
vector<int> val = A;
val.insert(val.end(), all(V));
sort(all(val));
compact(val);
for(auto &it : A) it = lower_bound(all(val), it) - val.begin();
for(auto &it : V) it = lower_bound(all(val), it) - val.begin();
int vals = sz(val);
segment_tree tr(vals);
vector<set<int, greater<int>>> online(vals);
for(int i = 0; i < N; ++i){
online[A[i]].insert(i);
}
for(int i = 0; i < vals; ++i){
if(!online[i].empty()){
tr.change(1, 0, vals - 1, i, *online[i].begin());
tr.add(1, 0, vals - 1, i, vals - 1, -sz(online[i]));
}
}
vector<int> S(Q);
for(int i = 0; i < Q; ++i){
tr.add(1, 0, vals - 1, A[X[i]], vals - 1, +1);
online[A[X[i]]].erase(X[i]);
if(online[A[X[i]]].empty()) tr.change(1, 0, vals - 1, A[X[i]], -inf);
else tr.change(1, 0, vals - 1, A[X[i]], *online[A[X[i]]].begin());
A[X[i]] = V[i];
tr.add(1, 0, vals - 1, A[X[i]], vals - 1, -1);
online[A[X[i]]].insert(X[i]);
tr.change(1, 0, vals - 1, A[X[i]], *online[A[X[i]]].begin());
S[i] = tr.query() + 1;
}
return S;
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
file("task");
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];
}
vector<int> S = countScans(A, X, V);
for(auto it : S) cout << it << '\n';
return 0;
}
#endif //LOCAL
