#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 2e5+5;
const int INF = 1e9+1e8;
struct l_seg_tree
{
vector<int> tree;
vector<int> lazy;
void init(int n)
{
tree.assign(4*n+14, -INF);
lazy.assign(4*n+14, 0);
return;
}
void push(int id)
{
if(lazy[id] == 0)
return;
tree[2*id]+=lazy[id]; tree[2*id+1]+=lazy[id];
lazy[2*id]+=lazy[id]; lazy[2*id+1]+=lazy[id];
lazy[id] = 0;
return;
}
void upd(int D, int ql, int qr, int id, int l, int r)
{
if(qr < l || r < ql)
return;
if((ql <= l) && (r <= qr))
{
tree[id]+=D;
lazy[id]+=D;
return;
}
push(id);
int m = (l+r)/2;
upd(D, ql, qr, 2*id, l, m);
upd(D, ql, qr, 2*id+1, m+1, r);
tree[id] = max(tree[2*id], tree[2*id+1]);
return;
}
int ans()
{
return tree[1];
}
};
l_seg_tree work;
void alive(int x, int N)
{
work.upd(INF, x, x, 1, 1, N);
if(x > 1)
work.upd(1, 1, x-1, 1, 1, N);
return;
}
void unalive(int x, int N)
{
work.upd(-INF, x, x, 1, 1, N);
if(x > 1)
work.upd(-1, 1, x-1, 1, 1, N);
return;
}
vector<int> countScans(vector<int> A, vector<int> x, vector<int> v)
{
int n = A.size();
vector<in> G;
for(int i = 0; i < n; i++)
G.pb({A[i], i});
for(int i = 0; i < v.size(); i++)
G.pb({v[i], x[i]});
sort(G.begin(), G.end());
vector<in> H; H.pb({-INF, -INF});
for(auto s: G)
{
if(s != H.back())
H.pb(s);
}
vector<int> a(n+1);
for(int i = 1; i <= n; i++)
a[i] = lower_bound(H.begin(), H.end(), (in){A[i-1], i-1}) - H.begin();
int q = x.size();
for(int i = 0; i < q; i++)
v[i] = lower_bound(H.begin(), H.end(), (in){v[i], x[i]}) - H.begin();
/*for(int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
for(int i = 0; i < q; i++)
cout << x[i] << " " << v[i] << " ";
cout << endl;*/
int N = H.size()-1;
work.init(N);
for(int i = 1; i <= N; i++)
work.upd(H[i][1]+1-n, i, i, 1, 1, N);
for(int i = 1; i <= n; i++)
alive(a[i], N);
vector<int> ans(q);
for(int s = 0; s < q; s++)
{
x[s]++;
unalive(a[x[s]], N);
a[x[s]] = v[s];
alive(a[x[s]], N);
ans[s] = work.ans();
}
return ans;
}
