//little anger, how blessing to be capable of fireeee
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
using ll = long long;
const ll rinf = -2000000000ll;
const ll ninf = -2003000000ll;
int aq;
vector<pair<int, int>> qrss;
ll laz[4000005], segm[4000005], segs[4000005];
void plaz(int idx, int cnt) {
segm[idx] += laz[idx];
if(cnt > 1) {
laz[idx*2+1] += laz[idx];
laz[idx*2+2] += laz[idx];
}
laz[idx]=0;
}
void updset(int idx, int l, int r, int tgt, int val) {
plaz(idx, r-l+1);
if(l == r) {
segm[idx] = val;
segs[idx] = (val > rinf);
return;
}
int mid = (l+r) >> 1;
if(tgt <= mid) updset(idx*2+1, l, mid, tgt, val);
else updset(idx*2+2, mid+1, r, tgt, val);
plaz(idx*2+1, mid-l+1); plaz(idx*2+2, r-mid);
segm[idx] = max(segm[idx*2+1], segm[idx*2+2]);
//printf("Set segm[%d] = %lld\n", idx, segm[idx]);
//printf("It's from %lld and %lld\n", segm[idx*2+1], segm[idx*2+2]);
segs[idx] = segs[idx*2+1] + segs[idx*2+2];
}
void updrng(int idx, int l, int r, int tl, int tr, int val) {
plaz(idx, r-l+1);
if(tl <= l && r <= tr) {
laz[idx] += val;
plaz(idx, r-l+1);
//cout << "INstant " << idx << " -> " << segm[idx] << '\n';
return;
}
if(tr < l || r < tl) return ;
int mid = (l+r) >> 1;
updrng(idx*2+1, l, mid, tl, tr, val);
updrng(idx*2+2, mid+1, r, tl, tr, val);
segm[idx] = max(segm[idx*2+1], segm[idx*2+2]);
//printf("Set segm[%d] = %lld\n", idx, segm[idx]);
//printf("It's from %lld and %lld\n", segm[idx*2+1], segm[idx*2+2]);
}
ll qrs(int idx, int l, int r, int tl, int tr) {
plaz(idx, r-l+1);
if(tl <= l && r <= tr) return segs[idx];
if(r < tl || tr < l) return 0;
int mid = (l+r) >> 1;
return qrs(idx*2+1, l, mid, tl, tr) + qrs(idx*2+2, mid+1, r, tl, tr);
}
ll qrm(int idx, int l, int r, int tl, int tr) {
plaz(idx, r-l+1);
if(tl <= l && r <= tr) return segm[idx];
if(r < tl || tr < l) return ninf;
int mid = (l+r) >> 1;
return max(qrm(idx*2+1, l, mid, tl, tr), qrm(idx*2+2, mid+1, r, tl, tr));
}
void addElem(int x, int v) {
//assumes element is currently not there
auto idx = lower_bound(qrss.begin(), qrss.end(), make_pair(v, x)) - qrss.begin();
assert(qrss[idx] == make_pair(v, x));
int bfs = qrs(0, 0, aq, 0, idx);
//cout << "HEYHEY IM ADDINGHEYYYYYYYYYYYY\n";
updrng(0, 0, aq, idx, aq, -1);
//cout << "im adding -1 to " << idx << " til " << aq << '\n';
updset(0, 0, aq, idx, x-bfs);
}
void delElem(int x, int v) {
//assumes element is there
auto idx = lower_bound(qrss.begin(), qrss.end(), make_pair(v, x)) - qrss.begin();
assert(qrss[idx] == make_pair(v, x));
updset(0, 0, aq, idx, ninf);
int bfs = qrs(0, 0, aq, 0, idx);
updrng(0, 0, aq, idx, aq, 1);
//cout << "im adding 1 to " << idx << " til " << aq << '\n';
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int n = A.size(), q = X.size();
//vector<pair<int, int>> qrs;
qrss.clear();
for(int i=0;i<n;i++) qrss.emplace_back(A[i], i);
for(int i=0;i<q;i++) qrss.emplace_back(V[i], X[i]);
sort(qrss.begin(), qrss.end());
qrss.resize(unique(qrss.begin(), qrss.end()) - qrss.begin());
aq = qrss.size();
for(int i=0;i<=4*aq;i++) {
segm[i] = ninf;
laz[i] = segs[i] = 0;
}
for(int i=0;i<n;i++) {
addElem(i, A[i]);
}
//cout << segm[0] << "___"; for(int i=0;i<=aq;i++) cout << qrm(0, 0, aq, i, i) << ' '; cout << '\n';
vector<int> ans(q);
for(int i=0;i<q;i++) {
delElem(X[i], A[X[i]]);
A[X[i]]=V[i];
addElem(X[i], A[X[i]]);
//cout << segm[0] << "___";
ans[i] = max(0ll, qrm(0, 0, aq, 0, aq));
//for(int i=0;i<=aq;i++) cout << qrm(0, 0, aq, i, i) << ' ';
//cout << '\n';
}
return ans;
}
/*
int main() {
// your code goes here
//auto res = countScans({1,2,3,4},{0,2},{3,1});
auto res = countScans({1,2,3,4},{0,2},{0,1});
for(auto&e:res) cout << e << " ";
return 0;
}*/
