#include <bits/stdc++.h>
//#define DEBUG
#ifndef DEBUG
#include "bubblesort2.h"
#endif
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, int> p3i;
int N, Q;
class SegmentTree
{
public:
int N, sti, dri, val, pos;
int aint[4000005], add[4000005];
void lazy(int nod, int st, int dr)
{
if(!add[nod]) return;
aint[nod * 2] += add[nod];
add[nod * 2] += add[nod];
aint[nod * 2 + 1] += add[nod];
add[nod * 2 + 1] += add[nod];
add[nod] = 0;
}
void B(int nod, int st, int dr)
{
aint[nod] = -(1 << 30);
add[nod] = 0;
if(st == dr) return;
int mij = st + (dr - st) / 2;
B(nod * 2, st, mij);
B(nod * 2 + 1, mij + 1, dr);
}
void U(int nod, int st, int dr)
{
if(sti <= st && dr <= dri)
{
aint[nod] += val;
add[nod] += val;
return;
}
int mij = st + (dr - st) / 2;
lazy(nod, st, dr);
if(sti <= mij) U(nod * 2, st, mij);
if(mij < dri) U(nod * 2 + 1, mij + 1, dr);
aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
}
void Up(int nod, int st, int dr)
{
if(st == dr)
{
aint[nod] = val;
add[nod] = 0;
return;
}
int mij = st + (dr - st) / 2;
lazy(nod, st, dr);
if(pos <= mij) Up(nod * 2, st, mij);
else Up(nod * 2 + 1, mij + 1, dr);
aint[nod] = max(aint[nod * 2], aint[nod * 2 + 1]);
}
void build() { B(1, 1, N); }
int query() { return aint[1]; }
void update(int st, int dr, int _val)
{
if(st > dr) return;
sti = st, dri = dr, val = _val;
U(1, 1, N);
}
void updatepos(int _pos, int _val)
{
pos = _pos; val = _val;
Up(1, 1, N);
}
}aint;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
N = A.size(), Q = V.size();
vector<int> ret;
ret.resize(Q);
vector<p3i> nrm;
for(int i = 0; i < N; i++) nrm.push_back({ {A[i], i}, 0 });
for(int i = 0; i < Q; i++) nrm.push_back({ {V[i], X[i]}, i + 1 });
sort(nrm.begin(), nrm.end());
for(int i = 0; i < nrm.size(); i++)
{
int val = i + 1;
if(nrm[i].second == 0) A[ nrm[i].first.second ] = val;
else V[ nrm[i].second - 1 ] = val;
}
aint.N = N + Q;
aint.build();
for(int i = 0; i < N; i++)
aint.update(A[i], A[i], i + (1 << 30));
for(int i = 0; i < N; i++)
aint.update(A[i] + 1, N + Q, -1);
for(int q = 0; q < Q; q++)
{
int pos = X[q];
int val = V[q];
int lstval = A[pos];
A[pos] = val;
aint.update(lstval, lstval, -(1 << 30) - pos);
aint.update(lstval + 1, N + Q, 1);
aint.update(val, val, (1 << 30) + pos);
aint.update(val + 1, N + Q, -1);
ret[q] = aint.query();
}
return ret;
}
#ifdef DEBUG
int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
int N,Q;
N=readInt();
Q=readInt();
std::vector<int> A(N);
for(int i=0;i<N;i++)
A[i]=readInt();
std::vector<int> X(Q),V(Q);
for(int j=0;j<Q;j++){
X[j]=readInt();
V[j]=readInt();
}
std::vector<int> res=countScans(A,X,V);
for(int j=0;j<int(res.size());j++)
printf("%d\n",res[j]);
}
#endif
