// #include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using pii=pair<int,int>;
#define pb push_back
#define all(v) v.begin(),v.end()
vector<int> a;
int n;
struct Node{
int val=0;
int lazy=0;
Node* left,*right;
Node() : left(nullptr),right(nullptr) {}
};
Node* root;
void build(Node* node,int l,int r){
if(l==r) return;
int mid=(l+r)/2;
node->left=new Node();
node->right=new Node();
build(node->left,l,mid);
build(node->right,mid+1,r);
}
void push(Node* node,int l,int r){
if(node->lazy==0) return;
node->val+=node->lazy;
if(node->left) {
node->left->lazy+=node->lazy;
}
if(node->right) {
node->right->lazy+=node->lazy;
}
node->lazy=0;
}
void update(Node* node,int l,int r,int ql,int qr,int x){
push(node,l,r);
if(ql>r||qr<l) return;
if(ql<=l&&r<=qr){
node->lazy+=x;
push(node,l,r);
return;
}
int mid=(l+r)/2;
update(node->left,l,mid,ql,qr,x);
update(node->right,mid+1,r,ql,qr,x);
push(node,l,r);
node->val=max(node->left->val,node->right->val);
}
vector<int> countScans(vector<int> A,vector<int> x,vector<int> y){
a=A;
root=new Node();
n=a.size();
int q=x.size();
build(root,0,n+q);
vector<pii> v;
for(int i=0;i<n;i++){
v.pb({a[i],i});
}
for(int i=0;i<q;i++){
v.pb({y[i],x[i]});
}
sort(all(v));
map<pii,int> mp;
for(int i=0;i<n+q;i++){
mp[v[i]]=i;
}
for(int i=0;i<n;i++){
a[i]=mp[{a[i],i}];
}
for(int i=0;i<q;i++){
y[i]=mp[{y[i],x[i]}];
}
vector<int> Ans(q);
int sz=n+q;
auto ch = [&](int i,int x){
update(root,0,sz,a[i],a[i],i*x);
update(root,0,sz,a[i]+1,sz,-x);
};
for(int i=0;i<n;i++){
ch(i,1);
}
for(int i=0;i<q;i++){
ch(x[i],-1);
a[x[i]]=y[i];
ch(x[i],1);
Ans[i]=root->val;
}
return Ans;
}
#ifdef IOI
// #include "bubblesort2.h"
// #include <cstdio>
// #include <cstdlib>
// #include <vector>
int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
int N,Q;
N=readInt();
Q=readInt();
vector<int> A(N);
for(int i=0;i<N;i++)
A[i]=readInt();
vector<int> X(Q),V(Q);
for(int j=0;j<Q;j++){
X[j]=readInt();
V[j]=readInt();
}
vector<int> res=countScans(A,X,V);
for(int j=0;j<int(res.size());j++)
printf("%d\n",res[j]);
}
#endif
