#include "bubblesort2.h"
#include <bits/stdc++.h>
#define mid ((st+dr)>>1)
#define left_son (node<<1)
#define right_son ((node<<1)|1)
using namespace std;
const int Nmax = 1e6 + 5, lim = 1e6, inf = 1e6;
typedef long long ll;
ll a[Nmax], val[Nmax];
class SegmentTree
{
int lazy[Nmax<<2], a[Nmax<<2];
public:
void add(int node, int st, int dr, int L, int R, int Add)
{
if(L <= st && dr <= R)
{
lazy[node] += Add;
return;
}
if(L <= mid) add(left_son, st, mid, L, R, Add);
if(mid < R) add(right_son, mid+1, dr, L, R, Add);
a[node] = max(a[left_son] + lazy[left_son], a[right_son] + lazy[right_son]);
}
int query()
{
return a[1] + lazy[1];
}
void init(int node, int st, int dr)
{
a[node] = -inf; lazy[node] = 0;
if(st == dr) return;
init(left_son, st, mid); init(right_son, mid+1, dr);
}
} aint;
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int N = A.size(), i;
int Q = V.size();
map<ll, int> mp;
for(i=0; i<N; ++i) a[i] = (ll) lim * A[i] + i;
for(i=0; i<Q; ++i) val[i] = (ll) lim * V[i] + X[i];
for(i=0; i<N; ++i) mp[a[i]] = 1;
for(i=0; i<Q; ++i) mp[val[i]] = 1;
int cnt = 0;
for(auto &it : mp) it.second = ++cnt;
aint.init(1, 1, cnt);
for(i=0; i<N; ++i)
{
int pos = mp[a[i]];
aint.add(1, 1, cnt, pos, pos, +inf+i);
aint.add(1, 1, cnt, 1, pos, +1);
}
vector<int> answer(Q);
for(i=0; i<Q; ++i)
{
int pos = mp[a[X[i]]];
aint.add(1, 1, cnt, 1, pos, -1);
aint.add(1, 1, cnt, pos, pos, -inf-X[i]);
a[X[i]] = val[i];
int act = mp[val[i]];
aint.add(1, 1, cnt, act, act, +inf+X[i]);
aint.add(1, 1, cnt, 1, act, 1);
answer[i] = aint.query() - N;
}
return answer;
}
