#include <bits/stdc++.h>
#define ll long long
#include "bubblesort2.h"
using namespace std;
const int N = 1e6 + 5;
const int oo = -1e9;
int n, m, q, a[N], _x[N], _y[N], kq[N], pos[N];
int st[N << 2], lz[N << 2], le[N], ri[N];
void build(int i,int l,int r){
if(l == r){
st[i] = oo;
return;
}
int mid = (l + r) / 2;
build(i << 1, l, mid);
build(i << 1|1, mid + 1, r);
st[i] = max(st[i << 1], st[i << 1|1]);
}
void dolz(int i){
if(!lz[i]) return;
int x = lz[i]; lz[i] = 0;
lz[i << 1] += x;
lz[i << 1|1] += x;
st[i << 1] += x;
st[i << 1|1] += x;
}
void update(int i,int l,int r,int u,int v,int x){
if(l > r || r < u || v < l) return;
if(u <= l && r <= v){
st[i] += x;
lz[i] += x;
return;
}
dolz(i);
int mid = (l + r) / 2;
update(i << 1, l, mid, u, v, x);
update(i << 1|1, mid + 1, r, u, v, x);
st[i] = max(st[i << 1], st[i << 1|1]);
}
void change(int i,int l,int r,int u,int val){
if(l > r || r < u || u < l) return;
if(l == r){
st[i] = val;
lz[i] = 0;
return;
}
dolz(i);
int mid = (l + r) / 2;
change(i << 1, l, mid, u, val);
change(i << 1|1, mid + 1, r, u, val);
st[i] = max(st[i << 1], st[i << 1|1]);
}
int b[N], T[N];
void inc(int x,int val){
for(int i = x; i <= m; i += i & (-i)) T[i] += val;
}
int query(int x){
int ret = 0;
for(int i = x; i; i -= i & (-i)) ret += T[i];
return ret;
}
int c[N];
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
n = A.size();
for(int i = 0; i < n; i ++){
a[i + 1] = A[i];
c[++m] = i + 1;
}
q = X.size();
for(int k = 0; k < q; k ++){
_x[k + 1] = X[k] + 1, _y[k + 1] = V[k];
c[++m] = n + k + 1;
a[n + k + 1] = _y[k + 1];
}
sort(c + 1, c + m + 1, [&](int x,int y){return a[x] < a[y];});
int last = 1;
for(int i = 1; i <= m; i ++){
if(a[c[i]] != a[c[i - 1]]) last = i;
le[i] = last;
pos[c[i]] = i;
}
last = m;
for(int i = m; i >= 1; i --){
if(a[c[i]] != a[c[i + 1]]) last = i;
ri[i] = last;
}
// for(int i = 1; i <= m; i ++) cerr << i << " " << pos[i] << " " << le[pos[i]] << " " << ri[pos[i]] << " k\n";
build(1, 1, m);
for(int i = 1; i <= n; i ++){
change(1, 1, m, pos[i], i);
inc(pos[i], 1);
}
for(int i = 1; i <= n; i ++){
update(1, 1, m, le[pos[i]], m, -1);
b[i] = i;
}
for(int k = 1; k <= q; k ++){
int x = _x[k];
int y = _y[k];
int tmp = pos[n + k];
update(1, 1, m, le[pos[b[x]]], m, +1);
change(1, 1, m, pos[b[x]], oo);
inc(pos[b[x]], -1);
inc(tmp, 1);
update(1, 1, m, le[tmp], m, -1);
change(1, 1, m, tmp, x - query(ri[tmp]));
b[x] = n + k;
kq[k] = st[1];
}
std::vector<int> answer(q);
for(int j = 0; j < q; j ++) {
answer[j] = kq[j + 1];
}
return answer;
}
//#define LOCAL
#ifdef LOCAL
int _n, _q;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
cin >> _n >> _q;
std::vector<int> A(_n);
for(int i = 0; i < _n; i ++)
cin >> A[i];
std::vector<int> X(_q),V(_q);
for(int j = 0; j < _q ; j++){
cin >> X[j] >> V[j];
}
std::vector<int> res=countScans(A,X,V);
for(int j=0;j<int(res.size());j++)
cout << res[j] << "\n";
}
/*
4 2
1 2 3 4
0 3
2 1
*/
#endif // LOCAL
