#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;
const int S = 1024;
const int N = 500'032 + S;
int seg_mx[N/S][S*2-1];
int seg_cnt[N/S][S*2-1];
int val[N], cnt[N], val_srt[N], srt_ind[N];
int n;
void add_seg(int l, int r, int x, int t, int i, int b, int e)
{
if (l <= b && e <= r) {
seg_cnt[t][i] += x;
seg_mx[t][i] += x;
return;
}
if (r <= b || e <= l)
return;
add_seg(l, r, x, t, 2*i+1, b, (b+e)/2);
add_seg(l, r, x, t, 2*i+2, (b+e)/2, e);
seg_mx[t][i] = max(seg_mx[t][2*i+1], seg_mx[t][2*i+2]);
seg_mx[t][i] += seg_cnt[t][i];
}
void build_seg(int t, int i, int b, int e)
{
if (e-b == 1) {
seg_cnt[t][i] = cnt[srt_ind[b]];
seg_mx[t][i] = seg_cnt[t][i];
return;
}
build_seg(t, 2*i+1, b, (b+e)/2);
build_seg(t, 2*i+2, (b+e)/2, e);
seg_cnt[t][i] = 0;
seg_mx[t][i] = max(seg_mx[t][2*i+1], seg_mx[t][2*i+2]);
}
void flush_seg(int t, int i, int b, int e)
{
if (e-b == 1) {
cnt[srt_ind[b]] = seg_cnt[t][i];
return;
}
seg_cnt[t][2*i+1] += seg_cnt[t][i];
seg_cnt[t][2*i+2] += seg_cnt[t][i];
seg_cnt[t][i] = 0;
flush_seg(t, 2*i+1, b, (b+e)/2);
flush_seg(t, 2*i+2, (b+e)/2, e);
}
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;
xr = lower_bound(val_srt + l, val_srt + l + S, xr) - val_srt;
if (xl < xr)
add_seg(xl, xr, val, l/S, 0, l, l + S);
}
void mov(int i, int x)
{
int j = i - i%S;
for (; srt_ind[j] != i; ++j);
val_srt[j] = x;
while ((j+1)%S && val_srt[j] > val_srt[j+1]) {
swap(val_srt[j], val_srt[j+1]);
swap(srt_ind[j], srt_ind[j+1]);
++j;
}
while (j%S && val_srt[j] < val_srt[j-1]) {
swap(val_srt[j], val_srt[j-1]);
swap(srt_ind[j], srt_ind[j-1]);
--j;
}
}
void up(int i, int x)
{
int pre = val[i];
int cnt_gt = 0;
for (int l = 0; l < i - i%S; l += S)
cnt_gt += get_gt(l, x);
flush_seg(i/S, 0, i - i%S, i - i%S + 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, 0, i - i%S, i - i%S + S);
int val = pre < x? 1: -1;
int xl = pre < x? pre: x;
int xr = pre < x? x: pre;
for (int l = i - i%S + S; l < n; l += S)
up_range(l, xl, xr, val);
}
int get()
{
int mx = 0;
for (int l = 0; l < n; l += S)
mx = max(seg_mx[l/S][0], mx);
return mx;
}
void init(vector<int> A)
{
n = A.size();
fill(val, val+N, (int)1e9 + 10);
fill(val_srt, val_srt+N, (int)1e9 + 10);
iota(srt_ind, srt_ind+N, 0);
memset(seg_cnt, 0, sizeof(seg_cnt));
memset(seg_mx, 0, sizeof(seg_mx));
memset(cnt, 0, sizeof(cnt));
Loop (i,0,n)
up(i, A[i]);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
init(A);
vector<int> ans;
Loop (i,0,X.size()) {
up(X[i], V[i]);
ans.push_back(get());
}
return ans;
}
