#if not LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>
const int inf=1e9+9;
struct SegmentTree {
std::vector<int64_t> nodes, lazy;
std::vector<int> L, H;
void buildRange(int node, int low, int high) {
L[node]=low, H[node]=high;
nodes[node]=lazy[node]=0;
if (low==high) {
return ;
}
int mid=(low+high)>>1;
buildRange(node<<1, low, mid);
buildRange(node<<1|1, mid+1, high);
}
SegmentTree(int n) {
nodes.resize(n<<2); lazy.resize(n<<2);
L.resize(n<<2), H.resize(n<<2);
buildRange(1, 1, n);
}
void propagate(int node) {
auto& t=lazy[node];
nodes[node<<1]+=t;
lazy[node<<1]+=t;
nodes[node<<1|1]+=t;
lazy[node<<1|1]+=t;
t=0;
}
void update(int node, int leftq, int rightq, int delta) {
//std::cout<<node<<" "<<L[node]<<" "<<H[node]<<" "<<leftq<<" "<<rightq<<" "<<delta<<"\n";
if (leftq<=L[node] and rightq>=H[node]) {
nodes[node]+=delta;
lazy[node]+=delta;
return ;
}
propagate(node);
if (H[node<<1]>=leftq) update(node<<1, leftq, rightq, delta);
if (L[node<<1|1]<=rightq) update(node<<1|1, leftq, rightq, delta);
nodes[node]=std::max(nodes[node<<1], nodes[node<<1|1]);
}
};
std::vector<int> countScans(std::vector<int> a, std::vector<int> x, std::vector<int> v) {
int n=a.size(), q=v.size();
std::vector< std::pair<int, int> > num;
for (int i=0; i<n; i++) {
num.push_back({a[i], i});
}
for (int i=0; i<q; i++) {
num.push_back({v[i], x[i]});
}
std::sort(begin(num), end(num));
num.erase(std::unique(begin(num), end(num)), end(num));
int s=num.size();
//std::cout<<s<<"\n";
SegmentTree seg(s);
seg.update(1, 1, s, -inf);
const auto ins=[&](int p, int r) {
int i=std::lower_bound(begin(num), end(num), std::make_pair(p, r))-begin(num)+1;
seg.update(1, i, i, inf+r);
if (i<s) {
seg.update(1, i+1, s, -1);
}
};
const auto ers=[&](int p, int r) {
int i=std::lower_bound(begin(num), end(num), std::make_pair(p, r))-begin(num)+1;
seg.update(1, i, i, -inf-r);
if (i<s) {
seg.update(1, i+1, s, 1);
}
};
for (int i=0; i<n; i++) {
ins(a[i], i);
}
std::vector<int> result(q);
for (int i=0; i<q; i++) {
ers(a[x[i]], x[i]);
ins(v[i], x[i]);
a[x[i]]=v[i];
result[i]=seg.nodes[1];
}
return result;
}
/*int main() {
std::ios_base::sync_with_stdio(0); std::cin.tie(0);
int n, q; std::cin>>n>>q;
std::vector<int> a(n), x(q), v(q);
for (auto& _: a) std::cin>>_;
for (int i=0; i<q; i++) std::cin>>x[i]>>v[i];
auto result=countScans(a, x, v);
for (int i=0; i<q; i++) std::cout<<result[i]<<" ";
std::cout<<std::endl;
return 0;
}*/
/*
4 2
1 2 3 4
0 3
2 1
*/
