#include "teams.h"
#include <iostream>
#include <utility>
#include <algorithm>
const int SZ = (1 << 20) + 5, SZ2 = 500005;
int n, seg[SZ], lazy[SZ], pref[SZ2], suf[SZ2];
using namespace std;
void build(int idx, int L, int R)
{
if (L <= R)
{
if (L == R) {seg[idx] = pref[L - 1];}
else
{
int M = L + R >> 1;
build(2 * idx, L, M);
build(2 * idx + 1, M + 1, R);
seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
}
}
}
inline void prop(int idx, int L, int R)
{
if (L <= R && lazy[idx])
{
seg[idx] += lazy[idx];
if (L < R)
{
lazy[2 * idx] += lazy[idx];
lazy[2 * idx + 1] += lazy[idx];
}
lazy[idx] = 0;
}
}
inline void upd(int idx, int L, int R, int l, int r, int v)
{
l = max(L, l); r = min(R, r);
prop(idx, L, R);
if (l <= r)
{
if (L == l && R == r) {lazy[idx] += v; prop(idx, L, R);}
else
{
int M = L + R >> 1;
upd(2 * idx, L, M, l, r, v);
upd(2 * idx + 1, M + 1, R, l, r, v);
seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
}
}
}
void init(int N, int A[], int B[])
{
n = N;
for (int i = 0; i < n; i++) {pref[B[i]]++; suf[A[i]]++;}
for (int i = 1; i <= n + 1; i++) {pref[i] += pref[i - 1];}
for (int i = n; i >= 0; i--) {suf[i] += suf[i + 1];}
build(1, 1, n);
}
int can(int M, int K[])
{
sort(K, K + M);
for (int i = 0; i < M; i++)
{
upd(1, 1, n, 1, K[i], K[i]);
upd(1, 1, n, 1, K[i], suf[K[i] + 1]);
if (seg[1] > n) {return 0;}
upd(1, 1, n, 1, K[i], -suf[K[i] + 1]);
}
for (int i = 0; i < M; i++)
{
upd(1, 1, n, 1, K[i], -K[i]);
}
return 1;
}
