#include "bubblesort2.h"
#include <vector>
#include <algorithm>
#include <iostream>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 1e6 + 12;
int n, q, m, t[N * 4], tt[N * 4];
vector< pair<int, int> > ord;
void push(int v){
if(!tt[v])
return;
t[v * 2] += tt[v], t[v * 2 + 1] += tt[v];
tt[v * 2] += tt[v], tt[v * 2 + 1] += tt[v];
tt[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int val){
if(tl > r || l > tr)
return;
if(tl >= l && tr <= r){
t[v] += val, tt[v] += val;
return;
}
push(v);
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, l, r, val);
upd(v * 2 + 1, tm + 1, tr, l, r, val);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int get_pos(pair<int, int> x){
return lower_bound(ord.begin(), ord.end(), x) - ord.begin() + 1;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n = A.size(), q = X.size();
for(int i = 0;i < n;i++)
ord.push_back(MP(A[i], i));
for(int i = 0;i < q;i++)
ord.push_back(MP(V[i], X[i]));
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
m = (int)ord.size();
for(int i = 0;i < n;i++){
int pos1 = get_pos(MP(A[i], i));
upd(1, 1, m, pos1, pos1, i + 1);
int pos2 = get_pos(MP(A[i], -1));
upd(1, 1, m, pos2, m, -1);
}
vector<int> answer(q);
for(int i = 0;i < q;i++){
int pos1 = get_pos(MP(A[X[i]], X[i]));
upd(1, 1, m, pos1, pos1, -X[i] - 1);
int pos2 = get_pos(MP(A[X[i]], -1));
upd(1, 1, m, pos2, m, 1);
A[X[i]] = V[i];
pos1 = get_pos(MP(A[X[i]], X[i]));
upd(1, 1, m, pos1, pos1, X[i] + 1);
pos2 = get_pos(MP(A[X[i]], -1));
upd(1, 1, m, pos2, m, -1);
answer[i] = t[1];
}
return answer;
}
