#include "bubblesort2.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
const int S = 2048 + 512;
const int N = 500'032 + S;
int seg_mx[S*2];
int seg_cnt[S*2];
int qans[N], added_to[N];
int val[N], val_copy[N], cnt[N], val_srt[N], srt_ind[N];
int n;
void add_seg(int l, int r, int x)
{
#define MAX(x, y) ((x)>(y)?(x):(y))
#define UP(i) seg_mx[i] = MAX(seg_mx[2*(i)],\
seg_mx[2*(i)+1])\
+ seg_cnt[i];
l += S; r += S;
for (;;) {
if (l != r && (l&1)) {
seg_mx[l] += x;
seg_cnt[l] += x;
++l;
}
if (l != r && (r&1)) {
--r;
seg_mx[r] += x;
seg_cnt[r] += x;
}
l /= 2; r /= 2;
if (l == 0) break;
if (l > 1) UP(l-1);
if (r < S) UP(r);
}
}
void build_seg(int l)
{
Loop (i,S,2*S) {
seg_cnt[i] = cnt[srt_ind[l + i-S]];
seg_mx[i] = seg_cnt[i];
}
LoopR (i,1,S) {
seg_mx[i] = max(seg_mx[2*i], seg_mx[2*i+1]);
seg_cnt[i] = 0;
}
}
void flush_seg(int l)
{
Loop (i,1,S) {
seg_cnt[2*i] += seg_cnt[i];
seg_cnt[2*i+1] += seg_cnt[i];
}
Loop (i,S,2*S)
cnt[srt_ind[l + i-S]] = seg_cnt[i];
}
int get_gt(int l, int x)
{
return S - ( upper_bound(val_srt + l, val_srt + l + S, x)
- (val_srt + l));
}
void up_range(int l, int xl, int xr, int val)
{
xl = lower_bound(val_srt + l, val_srt + l + S, xl) - val_srt - l;
xr = lower_bound(val_srt + l, val_srt + l + S, xr) - val_srt - l;
if (xl < xr)
add_seg(xl, xr, val);
}
void mov(int i, int x)
{
int j = i - i%S;
for (; srt_ind[j] != i; ++j);
int dst = lower_bound(val_srt + i-i%S, val_srt + i-i%S + S, x)
- val_srt;
if (j < dst) {
--dst;
Loop (k, j, dst) {
val_srt[k] = val_srt[k+1];
srt_ind[k] = srt_ind[k+1];
}
} else {
LoopR (k, dst, j) {
val_srt[k+1] = val_srt[k];
srt_ind[k+1] = srt_ind[k];
}
}
val_srt[dst] = x;
srt_ind[dst] = i;
}
void up(int l, int qi, int i, int x)
{
int pre = val[i];
if (i < l) {
int val = pre < x? 1: -1;
int xl = pre < x? pre: x;
int xr = pre < x? x: pre;
up_range(l, xl, xr, val);
} else if (l <= i && i < l + S) {
int cnt_gt = added_to[qi];
flush_seg(i/S);
val[i] = x;
for (int j = i - i%S; j < i; ++j)
cnt_gt += val[j] > x;
cnt[i] = cnt_gt;
for (int j = i + 1; j < i - i%S + S; ++j)
cnt[j] += (x > val[j]) - (pre > val[j]);
mov(i, x);
build_seg(i/S);
} else {
added_to[qi] += get_gt(l, x);
}
}
namespace init {
int fen[N];
void fen_add(int i, int x)
{
++i;
while (i < N) {
fen[i] += x;
i += i & -i;
}
}
int fen_get(int r)
{
int ans = 0;
while (r > 0) {
ans += fen[r];
r -= r & -r;
}
return ans;
}
void init(vector<int> A)
{
static pii pii_srt[N];
n = A.size();
Loop (i,0,n) {
val[i] = A[i];
pii_srt[i] = {val[i], i};
}
Loop (i,n,N) {
val[i] = 1e9+10;
pii_srt[i] = {val[i], i};
}
for (int l = 0; l < n; l += S) {
sort(pii_srt+l, pii_srt+l+S);
Loop (i,l,l+S) {
val_srt[i] = pii_srt[i].first;
srt_ind[i] = pii_srt[i].second;
}
}
vector<int> cmp(val, val+N);
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
int mx = cmp.size() - 1;
Loop (i,0,n) {
int j = lower_bound(cmp.begin(), cmp.end(), val[i])
- cmp.begin();
cnt[i] = fen_get(mx-j);
fen_add(mx-j, 1);
}
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
init::init(A);
vector<int> ans;
memcpy(val_copy, val, sizeof(val_copy));
for (int l = 0; l < n; l += S) {
build_seg(l);
Loop (i,0,X.size()) {
up(l, i, X[i], V[i]);
qans[i] = max(qans[i], seg_mx[1]);
}
memcpy(val, val_copy, sizeof(val));
}
Loop (i,0,X.size())
ans.push_back(qans[i]);
return ans;
}
