#include "bubblesort2.h"
#include<vector>
#include<algorithm>
#define DIM 1000005
#define f first
#define s second
using namespace std;
static vector<int> sol;
struct str{
int p, val, ind, inds;
};
static str v[DIM];
static int lst[DIM];
static pair<int, int> aint[4 * DIM];
static int cmp1(str a, str b){
if(a.val == b.val){
return a.p < b.p;
}
return a.val < b.val;
}
static int cmp2(str a, str b){
return a.ind < b.ind;
}
static void update(int nod, int st, int dr, int p, int u, int val){
if(p <= st && dr <= u){
aint[nod].s += val;
}
else{
int mid = (st + dr) / 2;
aint[2 * nod].s += aint[nod].s;
aint[2 * nod + 1].s += aint[nod].s;
aint[nod].s = 0;
if(p <= mid){
update(2 * nod, st, mid, p, u, val);
}
if(u > mid){
update(2 * nod + 1, mid + 1, dr, p, u, val);
}
aint[nod].f = max(aint[2 * nod].f + aint[2 * nod].s, aint[2 * nod + 1].f + aint[2 * nod + 1].s);
}
}
vector<int> countScans(vector<int> a, vector<int> xq, vector<int> yq){
int n, q, i;
n = a.size();
q = xq.size();
sol.resize(q);
for(i = 1; i <= n; i++){
v[i] = {i, a[i - 1], i, 0};
}
for(i = 1; i <= q; i++){
v[i + n] = {xq[i - 1] + 1, yq[i - 1], i + n, 0};
}
sort(v + 1, v + n + q + 1, cmp1);
for(i = 1; i <= n + q; i++){
v[i].inds = i;
if(v[i].ind <= n){
update(1, 1, n + q, i, n + q, -1);
update(1, 1, n + q, i, i, v[i].p);
}
}
sort(v + 1, v + n + q + 1, cmp2);
for(i = 1; i <= n; i++){
lst[ v[i].p ] = v[i].inds;
}
for(i = n + 1; i <= n + q; i++){
update(1, 1, n + q, lst[ v[i].p ], n + q, 1);
update(1, 1, n + q, lst[ v[i].p ], lst[ v[i].p ], -v[i].p);
update(1, 1, n + q, v[i].inds, n + q, -1);
update(1, 1, n + q, v[i].inds, v[i].inds, v[i].p);
lst[ v[i].p ] = v[i].inds;
sol[i - n - 1] = aint[1].f + aint[1].s;
}
return sol;
}
