#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
#define FOR(i,a,b) for(int i = a ; i < b ; ++i)
const int N = 1e6 + 1;
const int inf = 1e9 + 1;
typedef pair<int,int> ii;
typedef vector<int> arr;
int tr[N << 1];
int lz[N << 1];
void app(int i,int v) {
tr[i] += v;
lz[i] += v;
}
void upd(int l,int r,int v) {
l += N - 1;
r += N;
int L = l;
int R = r - 1;
for(; l < r ; l >>= 1, r >>= 1) {
if (l & 1) app(l++,v);
if (r & 1) app(--r,v);
}
for(; L > 1 ; L >>= 1) tr[L >> 1] = max(tr[L],tr[L ^ 1]) + lz[L >> 1];
for(; R > 1 ; R >>= 1) tr[R >> 1] = max(tr[R],tr[R ^ 1]) + lz[R >> 1];
}
arr countScans(arr a,arr p,arr x) {
int n = a.size();
int q = p.size();
vector<ii> val;
FOR(i,0,n) val.pb(ii(a[i],i));
FOR(i,0,q) val.pb(ii(x[i],p[i]));
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
int m = val.size();
auto add = [&](int P) {
int p = lower_bound(val.begin(),val.end(),ii(a[P],P)) - val.begin() + 1;
upd(p,m,-1);
upd(p,p, P + 1);
};
auto rem = [&](int P) {
int p = lower_bound(val.begin(),val.end(),ii(a[P],P)) - val.begin() + 1;
upd(p,m, 1);
upd(p,p,-P - 1);
};
vector<int> res;
FOR(i,0,n) add(i);
FOR(i,0,q) {
rem(p[i]); a[p[i]] = x[i];
add(p[i]); res.push_back(tr[1]);
}
return res;
}
/*int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
arr v = countScans({1,2,3,4},{0,2},{3,1});
for(int x : v) cout << x << " ";
}*/
