#include "teams.h"
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, ll>
#define fst first
#define snd second
#define ppp pair<pii, pii>
const int SZ = (1 << 20) + 5, SZ2 = 500005;
using namespace std;
struct p_node
{
int v = 0, l = -1, r = -1;
p_node() {}
};
int n, suf[SZ2], seg[SZ], lazy[SZ];
vector<p_node> p_seg;
vector<int> dt[SZ2];
int p_idx[SZ2];
vector<ppp> ivl;
void p_build(int idx, int L, int R)
{
if (L < R)
{
int M = L + R >> 1;
p_seg.push_back(p_node()); p_seg.push_back(p_node());
p_seg[idx].l = p_seg.size() - 2, p_seg[idx].r = p_seg.size() - 1;
p_build(p_seg[idx].l, L, M);
p_build(p_seg[idx].r, M + 1, R);
}
}
void p_upd(int idx, int odx, int L, int R, int x)
{
if (L <= R)
{
if (L == x && x == R) {p_seg[idx].v = p_seg[odx].v + 1;}
else
{
int M = L + R >> 1;
p_seg.push_back(p_node());
if (x <= M)
{
p_seg[idx].l = p_seg.size() - 1;
p_seg[idx].r = p_seg[odx].r;
p_upd(p_seg[idx].l, p_seg[odx].l, L, M, x);
}
else
{
p_seg[idx].r = p_seg.size() - 1;
p_seg[idx].l = p_seg[odx].l;
p_upd(p_seg[idx].r, p_seg[odx].r, M + 1, R, x);
}
p_seg[idx].v = p_seg[p_seg[idx].l].v + p_seg[p_seg[idx].r].v;
}
}
}
int p_qry(int idx, int L, int R, int l, int r)
{
l = max(L, l); r = min(R, r);
if (l <= r)
{
if (L == l && R == r) {return p_seg[idx].v;}
else
{
int M = L + R >> 1;
return p_qry(p_seg[idx].l, L, M, l, r) + p_qry(p_seg[idx].r, M + 1, R, l, r);
}
}
return 0;
}
inline void prop(int idx, int L, int R)
{
if (L <= R && lazy[idx] != -1)
{
seg[idx] = p_seg[lazy[idx]].v;
if (L < R)
{
lazy[2 * idx] = p_seg[lazy[idx]].l;
lazy[2 * idx + 1] = p_seg[lazy[idx]].r;
}
lazy[idx] = -1;
}
}
void bld(int idx, int L, int R)
{
seg[idx] = 0; lazy[idx] = -1;
if (L < R)
{
int M = L + R >> 1;
bld(2 * idx, L, M);
bld(2 * idx + 1, M + 1, R);
}
}
void upds(int idx, int edx, int L, int R, int l, int r)
{
l = max(L, l); r = min(R, r);
prop(idx, L, R);
if (l <= r)
{
if (L == l && R == r)
{
lazy[idx] = edx;
prop(idx, L, R);
}
else
{
int M = L + R >> 1;
upds(2 * idx, p_seg[edx].l, L, M, l, r);
upds(2 * idx + 1, p_seg[edx].r, M + 1, R, l, r);
seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
}
}
}
void updi(int idx, int L, int R, int x, int v)
{
prop(idx, L, R);
if (L == x && x == R) {seg[idx] += v;}
else
{
int M = L + R >> 1;
if (x <= M) {updi(2 * idx, L, M, x, v);}
else {updi(2 * idx + 1, M + 1, R, x, v);}
seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
}
}
inline void getInterval(int idx, int edx, int L, int R, int l, int r)
{
l = max(L, l); r = min(r, R);
prop(edx, L, R);
if (l <= r)
{
if (L == l && R == r)
{
//cout << "Splitted : " << L << " " << R << "\n";
ivl.push_back({{idx, edx}, {L, R}});
}
else
{
int M = L + R >> 1;
getInterval(p_seg[idx].l, 2 * edx, L, M, l, r);
getInterval(p_seg[idx].r, 2 * edx + 1, M + 1, R, l, r);
}
}
}
inline int findPos(int idx, int edx, int L, int R, int x)
{
prop(edx, L, R);
//cout << "FindPos " << L << " " << R << " " << x << " " << p_seg[idx].v - seg[edx] << "\n";
if (L < R)
{
int M = L + R >> 1;
prop(2 * edx, L, M); prop(2 * edx + 1, M + 1, R);
if (p_seg[p_seg[idx].l].v - seg[2 * edx] >= x) {return findPos(p_seg[idx].l, 2 * edx, L, M, x);}
else {return findPos(p_seg[idx].r, 2 * edx + 1, M + 1, R, x - p_seg[p_seg[idx].l].v + seg[2 * edx]);}
}
else {return L;}
}
int qry(int idx, int edx, int L, int R, int l, int r)
{
l = max(L, l); r = min(r, R);
prop(edx, L, R);
if (l <= r)
{
if (L == l && R == r)
{
return p_seg[idx].v - seg[edx];
}
else
{
int M = L + R >> 1;
return qry(p_seg[idx].l, 2 * edx, L, M, l, r) + qry(p_seg[idx].r, 2 * edx + 1, M + 1, R, l, r);
}
}
return 0;
}
void init(int N, int A[], int B[])
{
n = N;
for (int i = 0; i < n; i++)
{
suf[A[i]]++;
dt[A[i]].push_back(B[i]);
}
p_seg.push_back(p_node());
p_idx[0] = p_seg.size() - 1;
p_build(p_idx[0], 1, n);
for (int i = 1; i <= n; i++)
{
p_idx[i] = p_idx[i - 1];
for (auto &x : dt[i])
{
int nidx = p_seg.size();
p_seg.push_back(p_node());
p_upd(nidx, p_idx[i], 1, n, x);
p_idx[i] = nidx;
}
}
for (int i = n; i >= 0; i--) {suf[i] += suf[i + 1];}
bld(1, 1, n);
}
int can(int M, int K[])
{
//cout << "New " << M << "\n";
upds(1, p_idx[0], 1, n, 1, n);
sort(K, K + M);
for (int i = 0; i < M; i++)
{
if (qry(p_idx[K[i]], 1, 1, n, K[i], n) < K[i]) {return 0;}
else
{
ivl.clear();
getInterval(p_idx[K[i]], 1, 1, n, K[i], n);
int L = K[i], v = K[i];
for (int i = 0; i < ivl.size(); i++)
{
if (p_seg[ivl[i].fst.fst].v - seg[ivl[i].fst.snd] < v)
{
v -= p_seg[ivl[i].fst.fst].v - seg[ivl[i].fst.snd];
L = ivl[i].snd.snd + 1;
}
else {L = findPos(ivl[i].fst.fst, ivl[i].fst.snd, ivl[i].snd.fst, ivl[i].snd.snd, v); break;}
}
//cout << "LOL: " << i << " " << L << " " << qry(p_idx[K[i]], 1, 1, n, K[i], L - 1) << "\n";
updi(1, 1, n, L, K[i] - qry(p_idx[K[i]], 1, 1, n, K[i], L - 1));
upds(1, p_idx[K[i]], 1, n, K[i], L - 1);
}
}
return 1;
}
