#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;
int Search(vector<ll> &a, ll val)
{
int st = 0, dr = a.size() - 1;
while(st <= dr)
if(a[mid] < val) st = mid+1;
else dr = mid-1;
return st + 1;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int N = A.size(), i;
int Q = V.size();
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];
vector<ll> vals;
for(i=0; i<N; ++i) vals.push_back(a[i]);
for(i=0; i<Q; ++i) vals.push_back(val[i]);
sort(vals.begin(), vals.end());
int cnt = vals.size();
aint.init(1, 1, cnt);
for(i=0; i<N; ++i)
{
int pos = Search(vals, (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 = Search(vals, 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 = Search(vals, 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;
}
