#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int cox[4] = {1, 0, -1, 0};
//const int coy[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 1e6 + 5, mxs = 3e5, sq = 500, mxv = 2e6 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
#include "bubblesort2.h"
int st[4 * mxn + 1], lz[4 * mxn + 1];
vt<pii>comp;
int bit[mxn + 1];
void updbit(int p, int v){
while(p <= sz(comp)){
bit[p] += v; p += p & (-p);
}
}
int getbit(int p){
int ans = 0;
while(p){
ans += bit[p]; p -= p & (-p);
}
return(ans);
}
void go(int nd, int v){
st[nd] += v; lz[nd] += v;
}
void push(int nd){
int &v = lz[nd];
go(nd << 1, v); go(nd << 1 | 1, v);
v = 0;
}
void pull(int nd){
st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
void updset(int nd, int l, int r, int id, int v){
if(l == r){
st[nd] = v; return;
}
int mid = (l + r) >> 1;
push(nd);
if(id <= mid)updset(nd << 1, l, mid, id, v);
else updset(nd << 1 | 1, mid + 1, r, id, v);
pull(nd);
}
void updadd(int nd, int l, int r, int ql, int qr, int v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
go(nd, v); return;
}
int mid = (l + r) >> 1;
push(nd);
updadd(nd << 1, l, mid, ql, qr, v); updadd(nd << 1 | 1, mid + 1, r, ql, qr, v);
pull(nd);
}
int find(int sus, int sus2){
return(lower_bound(ALL(comp), mpp(sus, sus2)) - comp.begin() + 1);
}
std::vector<int> countScans(std::vector<int> a,std::vector<int> x,std::vector<int> v){
for(int i = 0; i < sz(a); i++)comp.pb(mpp(a[i], i));
for(int i = 0; i < sz(x); i++)comp.pb(mpp(v[i], x[i]));
sort(ALL(comp)); comp.resize(unique(ALL(comp)) - comp.begin());
for(int i = 0; i < sz(a); i++){
updbit(find(a[i], i), 1);
}
for(int i = 1; i <= 4 * sz(comp); i++)st[i] = -inf;
for(int i = 0; i < sz(a); i++){
updset(1, 1, sz(comp), find(a[i], i), i - getbit(find(a[i], i)));
}
vt<int>res;
for(int i = 0; i < sz(v); i++){
int pos = x[i], val = v[i];
updset(1, 1, sz(comp), find(a[pos], pos), -inf);
updadd(1, 1, sz(comp), find(a[pos], pos) + 1, sz(comp), 1);
updbit(find(a[pos], pos), -1);
a[pos] = val;
updbit(find(a[pos], pos), 1);
updset(1, 1, sz(comp), find(a[pos], pos), pos - getbit(find(a[pos], pos)));
updadd(1, 1, sz(comp), find(a[pos], pos) + 1, sz(comp), -1);
res.pb(st[1] + 1);
}
return(res);
}
/*
#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();
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]);
}
*/
