#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e6 + 3; // e memorie putina, nu merge +5
int len;
namespace AINT {
int lazy[4 * nmax];
int maxx[4 * nmax];
namespace AIB {
#define lsb(x) (x & (-x))
int active[nmax];
int sum[nmax];
void upd(int x, int val) {
while(x <= len)
sum[x] += val, x += lsb(x);
}
int query(int x) {
int s = 0;
while(x > 0)
s += sum[x], x -= lsb(x);
return s;
}
void toggle(int poz) {
upd(poz, (active[poz] ^ 1) - active[poz]);
active[poz] ^= 1;
}
}
void apply(int node, int cl, int cr) {
maxx[node] += lazy[node];
int mid = cl + cr >> 1;
if(cl != cr)
lazy[2 * node] += lazy[node], lazy [2 * node + 1] += lazy[node];
lazy[node] = 0;
}
void prop(int node, int cl, int cr) {
apply(node, cl, cr);
int mid = cl + cr >> 1;
if(cl != cr) {
apply(2 * node, cl, mid);
apply(2 * node + 1, mid + 1, cr);
}
return;
}
void push(int poz, int val, int node = 1, int cl = 1, int cr = len) {
//cerr << poz << ' ' << cl << ' ' << cr << '\n';
prop(node, cl, cr);
if(cl == cr) {
maxx[node] = val;
return;
}
int mid = cl + cr >> 1;
if(poz <= mid)
push(poz, val, 2 * node, cl, mid);
else
push(poz, val, 2 * node + 1, mid + 1, cr);
maxx[node] = max(maxx[2 * node], maxx[2 * node + 1]);
return;
}
void add(int l, int r, int val = 1, int node = 1, int cl = 1, int cr = len) {
prop(node, cl, cr);
#warning incearca cu apply simplu
if(r < cl || cr < l)
return;
if(l <= cl && cr <= r) {
lazy[node] += val;
prop(node, cl, cr);
return;
}
int mid = cl + cr >> 1;
add(l, r, val, 2 * node, cl, mid);
add(l, r, val, 2 * node + 1, mid + 1, cr);
maxx[node] = max(maxx[2 * node], maxx[2 * node + 1]);
}
void erase(int poz) {
AIB::toggle(poz);
push(poz, - 2e6 - 5);
add(poz + 1, len);
}
void insert(int poz, int val) {
push(poz, val - AIB::query(poz));
add(poz + 1, len, -1);
AIB::toggle(poz);
}
void construct(int node = 1, int cl = 1, int cr = len) {
maxx[node] = -2e6 - 5;
if(cl == cr)
return;
int mid = cl + cr >> 1;
construct(2 * node, cl, mid);
construct(2 * node + 1, mid + 1, cr);
return;
}
}
namespace NORM {
map<pair<int,int>, int> norm;
void push(int v, int poz) {
norm[{v, poz}];
}
void init() {
int cnt = 1;
for(auto &x : norm)
x.second = cnt++;
len = norm.size() + 1;
}
int query(int v, int poz) {
return norm[{v, poz}];
}
};
vector<int> countScans(vector<int> a, vector<int> x, vector<int> y){
int n = a.size(), q = x.size();
vector<int> ans(q);
for(int i = 0; i < n; i++)
NORM::push(a[i], i);
for(int i = 0; i < q; i++)
NORM::push(y[i], x[i]);
NORM::init();
AINT::construct();
for(int i = 0; i < n; i++)
AINT::insert(NORM::query(a[i], i), i);
for(int i = 0; i < q; i++) {
AINT::erase(NORM::query(a[x[i]], x[i]));
AINT::insert(NORM::query(y[i], x[i]), x[i]);
a[x[i]] = y[i];
ans[i] = AINT::maxx[1];
}
return ans;
}
