#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+6;
const int MAX = 1e9;
#define pii pair<int,int>
#define PB push_back
#define ins insert
#define X first
#define Y second
pii arr[N];
vector<pii>v;
pair<int,pair<int,int>>que[N];
map<int,int>map2;
int tour[4*N][2];
void prop(int tr) {
tour[tr][0]+=tour[tr][1];
tour[tr*2][1]+=tour[tr][1];
tour[tr*2+1][1]+=tour[tr][1];
tour[tr][1]=0;
}
void update(int lef,int rig,int lef2,int rig2,int tr,int val) {
prop(tr);
if (lef > rig2 or rig < lef2) return;
if (lef>=lef2 and rig<=rig2) {
tour[tr][1]+=val;
prop(tr);
return;
}
int mid = (lef + rig) / 2;
update(lef,mid,lef2,rig2,tr*2,val);
update(mid+1,rig,lef2,rig2,tr*2+1,val);
tour[tr][0] = max(tour[tr*2][0],tour[tr*2][0]);
}
int main() {
int n,q,a,b;
cin>>n>>q;
int indx = 0;
for (int i=0;i<n;i++) {
cin>>arr[i].X;
arr[i].Y=indx;
v.PB({arr[i].X,indx});
indx++;
}
for (int i=0;i<q;i++) {
cin>>a>>b;
a--;
que[indx]={a,{b,indx}};
v.PB({b,indx});
indx++;
}
sort(v.begin(),v.end());
int rr=1;
while(rr<v.size()) rr*=2;
for (int i=1;i<rr*2;i++) tour[i][0]=-MAX;
int br=0;
for (int i=0;i<v.size();i++) {
int ind = v[i].Y;
tour[i+rr][0]+=ind;
if (ind<n) {
tour[i+rr][0]=ind;
tour[i+rr][0]-= br;
//cout << ind <<" "<<br<<endl;
br++;
}
map2[ind] = i;
}
for (int i=rr-1;i>=1;i--) {
tour[i][0] = max(tour[i*2][0],tour[i*2+1][0]);
//cout << tour[i][0]<<" "<<i<<endl;
}
for (int i=n;i<n+q;i++) {
indx = i;
int tr = que[indx].X,val = que[indx].Y.X;
int taj = map2[arr[tr].Y] + 1;
int tt = (rr+taj-1) / 2;
update(1,rr,tt,tt,1,-MAX);
taj = map2[indx]+1;
update(1,rr,taj,taj,1,MAX);
//cout << tour[taj+rr-1][0]<<endl;
update(1,rr,taj,v.size(),1,-1);
prop(1);
cout << tour[1][0]<<endl;
}
return 0;
}
