#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=5e5+3;
int n,a[N],b[N],sf[N];
vector<pair<int,int>> vt;
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V) {
n=sz(A);
vector<int> res;
For(i,1,n) a[i]=A[i-1];
For(i,0,sz(X)-1) {
int x=X[i],v=V[i];
// x++;
a[x]=v;
sf[n+1]=2e9;
vt.clear();
For(j,1,n) vt.pb({a[j],j});
sort(all(vt));
For(j,1,n) b[vt[j-1].ss]=j;
ForD(j,n,1) sf[j]=max(sf[j],b[j]);
int ans=0;
For(j,1,n) {
int f=n+1;
if (j<n && b[n]>b[j]) {
int l=j+1,r=n;
while(l<r) {
int mid=l+(r-l)/2;
if (sf[mid]>b[j]) r=mid;
else l=mid+1;
}
f=l;
}
ans=max(ans,n-b[j]-(n-f+1));
}
res.pb(ans);
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N,Q;
cin >> N >> Q;
vector<int> x,y,z;
For(i,1,N) {
int k;
cin >> k;
x.pb(k);
}
For(i,1,Q) {
int k,k1;
cin >> k >> k1;
y.pb(k),z.pb(k1);
}
vector<int> ans=countScans(x,y,z);
for(auto x: ans) cout << x << endl;
return 0;
}
