#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
struct Node{
int n, lazy, org;
Node* nxt[4]; ///ll, lr, rl, rr
Node(){n = lazy = org = 0; fill(nxt, nxt+4, nullptr);}
~Node(){for (int i=0;i<4;i++) if (nxt[i]) delete nxt[i];}
void propagate(){
if (lazy==1) n = 0;
if (lazy==2) n = org;
if (lazy){
for (int i=0;i<4;i++) if (nxt[i]) nxt[i]->lazy = lazy;
}
lazy = 0;
}
void update1(int lx, int rx, int ly, int ry, int sx, int ex, int sy, int ey, int val){
propagate();
if (rx<sx || ex<lx) return;
if (ry<sy || ey<ly) return;
if (sx<=lx && rx<=ex && sy<=ly && ry<=ey){
lazy = val; propagate();
return;
}
int mx = (lx+rx)>>1, my = (ly+ry)>>1;
if (nxt[0]) nxt[0]->update1(lx, mx, ly, my, sx, ex, sy, ey, val);
if (nxt[1]) nxt[1]->update1(lx, mx, my+1, ry, sx, ex, sy, ey, val);
if (nxt[2]) nxt[2]->update1(mx+1, rx, ly, my, sx, ex, sy, ey, val);
if (nxt[3]) nxt[3]->update1(mx+1, rx, my+1, ry, sx, ex, sy, ey, val);
n = 0;
for (int i=0;i<4;i++) if (nxt[i]) n += nxt[i]->n;
}
void update2(int lx, int rx, int ly, int ry, int x, int y){
if (lx==rx && ly==ry) {n++, org++; return;}
int mx = (lx+rx)>>1, my = (ly+ry)>>1;
if (lx<=x && x<=mx && ly<=y && y<=my){
if (!nxt[0]) nxt[0] = new Node();
nxt[0]->update2(lx, mx, ly, my, x, y);
}
if (lx<=x && x<=mx && my+1<=y && y<=ry){
if (!nxt[1]) nxt[1] = new Node();
nxt[1]->update2(lx, mx, my+1, ry, x, y);
}
if (mx+1<=x && x<=rx && ly<=y && y<=my){
if (!nxt[2]) nxt[2] = new Node();
nxt[2]->update2(mx+1, rx, ly, my, x, y);
}
if (mx+1<=x && x<=rx && my+1<=y && y<=ry){
if (!nxt[3]) nxt[3] = new Node();
nxt[3]->update2(mx+1, rx, my+1, ry, x, y);
}
n = 0;
for (int i=0;i<4;i++) if (nxt[i]) n += nxt[i]->n;
org = n;
}
void update3(int lx, int rx, int ly, int ry, int x, int y, int val){
propagate();
if (lx==rx && ly==ry) {n -= val; return;}
int mx = (lx+rx)>>1, my = (ly+ry)>>1;
if (lx<=x && x<=mx && ly<=y && y<=my){
assert(nxt[0]);
nxt[0]->update3(lx, mx, ly, my, x, y, val);
}
if (lx<=x && x<=mx && my+1<=y && y<=ry){
assert(nxt[1]);
nxt[1]->update3(lx, mx, my+1, ry, x, y, val);
}
if (mx+1<=x && x<=rx && ly<=y && y<=my){
assert(nxt[2]);
nxt[2]->update3(mx+1, rx, ly, my, x, y, val);
}
if (mx+1<=x && x<=rx && my+1<=y && y<=ry){
assert(nxt[3]);
nxt[3]->update3(mx+1, rx, my+1, ry, x, y, val);
}
n = 0;
for (int i=0;i<4;i++) if (nxt[i]) n += nxt[i]->n;
}
int query(int lx, int rx, int ly, int ry, int sx, int ex, int sy, int ey){
//printf("Query: %d %d %d %d %d %d %d %d\n%d %d\n", lx, rx, ly, ry, sx, ex, sy, ey, n, org);
propagate();
if (rx<sx || ex<lx) return 0;
if (ry<sy || ey<ly) return 0;
if (sx<=lx && rx<=ex && sy<=ly && ry<=ey) return n;
int mx = (lx+rx)>>1, my = (ly+ry)>>1;
int ret = 0;
if (nxt[0]) ret += nxt[0]->query(lx, mx, ly, my, sx, ex, sy, ey);
if (nxt[1]) ret += nxt[1]->query(lx, mx, my+1, ry, sx, ex, sy, ey);
if (nxt[2]) ret += nxt[2]->query(mx+1, rx, ly, my, sx, ex, sy, ey);
if (nxt[3]) ret += nxt[3]->query(mx+1, rx, my+1, ry, sx, ex, sy, ey);
return ret;
}
};
Node* tree;
int N;
void init(int n, int A[], int B[]) {
N = n;
tree = new Node();
for (int i=0;i<n;i++){
tree->update2(1, n, 1, n, A[i], B[i]);
}
}
int can(int M, int K[]) {
int S = 0;
for (int i=0;i<M;i++) S += K[i];
if (S>N) return 0;
sort(K, K+M, greater<int>());
tree->update1(1, N, 1, N, 1, N, 1, N, 2);
for (int i=0;i<M;i++){
//printf("%d: ", i);
int chk = tree->query(1, N, 1, N, 1, K[i], K[i], N);
if (chk<K[i]) return 0;
int l = 1, r = K[i]+1, idx = 1e9;
//printf("%d ", tree->query(1, N, 1, N, 2, K[i], K[i], N));
while(l<r){
int m = (l+r)>>1;
if (tree->query(1, N, 1, N, m, K[i], K[i], N)>=K[i]) l = m+1, idx = m;
else r = m;
}
assert(idx!=1e9);
int tmp = K[i];
if (idx+1<=K[i]) tmp -= tree->query(1, N, 1, N, idx+1, K[i], K[i], N);
if (idx+1<=K[i]) tree->update1(1, N, 1, N, idx+1, K[i], K[i], N, 1);
l = K[i], r = N+1;
//printf("%d ", idx);
int idx2 = 1e9;
while(l<r){
int m = (l+r)>>1;
if (tree->query(1, N, 1, N, idx, idx, m, N)>=tmp) l = m+1, idx2 = m;
else r = m;
}
assert(idx2!=1e9);
//printf("%d\n", idx2);
int tmp2 = tmp;
if (idx2+1<=N) tmp2 -= tree->query(1, N, 1, N, idx, idx, idx2+1, N);
if (idx2+1<=N) tree->update1(1, N, 1, N, idx, idx, idx2+1, N, 1);
tree->update3(1, N, 1, N, idx, idx2, tmp2);
}
return 1;
}
