#include<bits/stdc++.h>
using namespace std;
const int N = 1000001;
vector<pair<int, int> > val;
int T[N << 2], SegTree[N << 2];
void push(int s, int l, int r) {
if (!SegTree[s]){
return;
}
T[s] += SegTree[s];
if (l != r) {
SegTree[s << 1] += SegTree[s];
SegTree[s << 1 | 1] += SegTree[s];
}
SegTree[s] = 0;
}
void up(int s, int l, int r, int from, int to, int val) {
push(s, l, r);
if (l > to || r < from) return;
if (from <= l && r <= to) {
SegTree[s] += val;
push(s, l, r);
return;
}
int mid = l + r >> 1;
up(s << 1, l, mid, from, to, val);
up(s << 1 | 1, mid + 1, r, from, to, val);
T[s] = max(T[s << 1], T[s << 1 | 1]);
}
vector<int> countScans(vector<int> a, vector<int> pos, vector<int> val2) {
vector<int> ans(pos.size());
int n = a.size();
for(int i = 0; i < n; i++){
val.push_back(make_pair(a[i], i));
}
for(int i = 0; i < pos.size(); i++){
val.push_back(make_pair(val2[i], pos[i]));
}
sort(val.begin(), val.end());
val.resize(unique(val.begin(), val.end()) - val.begin());
int m = val.size();
for(int i = 0; i < n; i++) {
int idx = upper_bound(val.begin(), val.end(), make_pair(a[i], i)) - val.begin();
up(1, 1, m, idx, idx, i + 1);
up(1, 1, m, idx, m, -1);
}
for(int i = 0; i < pos.size(); i++) {
int idx = upper_bound(val.begin(), val.end(), make_pair(a[pos[i]], pos[i])) - val.begin();
up(1, 1, m, idx, idx, -pos[i] - 1);
up(1, 1, m, idx, m, 1);
a[pos[i]] = val2[i];
idx = upper_bound(val.begin(), val.end(), make_pair(val2[i], pos[i])) - val.begin();
up(1, 1, m, idx, idx, pos[i] + 1);
up(1, 1, m, idx, m, -1);
ans[i] = T[1];
}
return ans;
}
