#include "bubblesort2.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
//#define int ll
#define sz(x) ((x).size())
using tii = tuple<int,int,int>;
using pii = pair<int,int>;
map<tii, int> nrm;
template<typename Node, typename Lazy>
struct AINT {
vector<Node> aint;
vector<Lazy> lazy;
int n;
void init(int _n) {
n = _n;
aint.resize(n * 2 + 5, Node());
lazy.resize(n * 2 + 5, Lazy());
}
void upd(int p, Node x, int node, int cl, int cr) {
if(p < cl || cr < p) return;
if(cl == cr) { aint[node] = x; return; }
int mid = cl + cr >> 1;
push(node, (mid - cl + 1) * 2);
upd(p, x, node + 1, cl, mid);
upd(p, x, node + (mid - cl + 1) * 2, mid + 1, cr);
aint[node] = aint[node + 1] + aint[node + (mid - cl + 1) * 2];
}
Node query(int l, int r, int node, int cl, int cr) {
if(r < cl || cr < l) return Node();
if(l <= cl && cr <= r) return aint[node];
int mid = cl + cr >> 1;
push(node, (mid - cl + 1) * 2);
return query(l, r, node + 1, cl, mid) + query(l, r, node + (mid - cl + 1) * 2, mid + 1, cr);
}
void upd(int p, Node x) { upd(p, x, 1, 1, n); }
Node query(int l, int r) { return query(l, r, 1, 1, n); }
void push(int node, int L) {
aint[node + 1] += lazy[node];
aint[node + L] += lazy[node];
lazy[node + 1] += lazy[node];
lazy[node + L] += lazy[node];
lazy[node] = Lazy();
}
void pushsegm(int l, int r, Lazy x, int node, int cl, int cr) {
if(cr < l || r < cl) return;
if(l <= cl && cr <= r) {
aint[node] += x;
lazy[node] += x;
return;
}
int mid = cl + cr >> 1;
push(node, (mid - cl + 1) * 2);
pushsegm(l, r, x, node + 1, cl, mid);
pushsegm(l, r, x, node + (mid - cl + 1) * 2, mid + 1, cr);
aint[node] = aint[node + 1] + aint[node + (mid - cl + 1) * 2];
}
void pushsegm(int l, int r, Lazy x) { return pushsegm(l, r, x, 1, 1, n); }
};
namespace Trolling {
int get(vector<int> V) {
int n = sz(V);
vector<int> idx(n);
iota(all(idx), 0);
sort(all(idx), [&](int a, int b) { return V[a] < V[b] || (V[a] == V[b] && a < b); } );
int mx = 0, cnt = 0;
for(auto x : idx)
// cerr << V[x] << ' ' << x << ' ' << cnt << '\n',
mx = max(mx, x - cnt),
cnt++;
return mx;
}
}
namespace DS {
struct Lazy {
int sum;
Lazy(int a = 0): sum(a) {;}
Lazy operator +(const Lazy &x) const { return Lazy(sum + x.sum); }
Lazy operator +=(const Lazy &x) { return *this = Lazy(sum + x.sum); }
};
struct Node {
int cnt, mx;
Node(int a = 0, int b = 0): cnt(a), mx(b) {;}
Node operator +(const Node& x) const { return Node(cnt + x.cnt, max(mx, x.mx)); }
Node operator +(const Lazy& x) const { return Node(cnt, mx + x.sum); }
Node operator +=(const Lazy& x) { return *this = Node(cnt, mx + x.sum); }
};
AINT<Node, Lazy> aint;
int n;
void init(int _n) {
aint.init(n = _n);
}
void insert(int a, int b, int c) {
int P = nrm[tii{a, b, c}];
int counter = aint.query(1, P).cnt;
aint.upd(P, Node(1, b - counter));
aint.pushsegm(P + 1, n, Lazy(-1));
// cerr << counter << ' ' << a << '\t' << b << '\t' << b - counter << '\n';
}
void erase(int a, int b, int c) {
int P = nrm[tii{a, b, c}];
aint.upd(P, Node(0, 0));
aint.pushsegm(P + 1, n, Lazy(1));
}
int query() {
// for(int i = 1; i <= n; i++)
// cerr << aint.query(i, i).cnt << ' ' << aint.query(i, i).mx << '\n';
return aint.query(1, n).mx;
}
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q=X.size(), n = sz(A);
vector<int> lastupdate(n, -1);
std::vector<int> answer(Q);
for(int i = 0; i < n; i++) {
nrm[tii{A[i], i, -1}];
}
for (int j=0;j<Q;j++) {
nrm[tii{V[j], X[j], j}];
}
int cnt = 1;
for(auto &[a, b] : nrm) b = cnt++;
DS::init(cnt - 1);
for(auto &[a, b] : nrm) {
auto [L, R, W] = a;
if(W == -1)
DS::insert(L, R, W);
}
for(int j = 0; j < Q; j++) {
DS::erase(A[X[j]], X[j], lastupdate[X[j]]);
lastupdate[X[j]] = j;
A[X[j]] = V[j];
DS::insert(A[X[j]], X[j], lastupdate[X[j]]);
answer[j] = DS::query();
}
return answer;
}
