#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<db, db> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int) (x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define resz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define f1r(i, a, b) for (int i = (a); i < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto& a : x)
const int LIM = 4e7;
#include "teams.h"
struct Node {
int lc, rc, sum;
} t[LIM];
int nodes = 0;
int modify(int p, int x, int v, int l, int r) {
int u = ++nodes;
if (l == r) {
t[u].sum = t[p].sum + v;
} else {
int m = (l+r)/2;
if (x <= m) {
t[u].lc = modify(t[p].lc, x, v, l, m);
t[u].rc = t[p].rc;
} else {
t[u].lc = t[p].lc;
t[u].rc = modify(t[p].rc, x, v, m+1, r);
}
t[u].sum = t[t[u].lc].sum+t[t[u].rc].sum;
}
return u;
}
int query(int p, int lo, int hi, int l, int r) {
if (lo > hi) return 0;
if (hi < l || r < lo) return 0;
if (lo <= l && r <= hi) return t[p].sum;
int m = (l+r)/2;
return query(t[p].lc, lo, hi, l, m) + query(t[p].rc, lo, hi, m+1, r);
}
int n;
vi a;
vi b;
vector<vpi> ri;
vector<vpi> le;
vi ti;
void init(int N, int A[], int B[]) {
n = N;
a.resize(n);
b.resize(n);
ri.resize(n+5);
le.resize(n+5);
ti.resize(n+5);
f0r(i, n) a[i] = A[i], b[i] = B[i];
f0r(i, n) ri[b[i]].eb(a[i], i);
f0r(i, n) le[a[i]].eb(b[i], i);
int cur_time = 0;
f1r(i, 1, n+1) {
for (auto& x : le[i]) {
cur_time = modify(cur_time, x.f, 1, 1, n);
}
ti[i] = cur_time;
}
}
int can(int M, int K[]) {
int m = M;
vi k(m);
f0r(i, m) k[i] = K[i];
sort(all(k));
vpi pv;
f0r(i, m) {
if (sz(pv) == 0 || pv.back().f != k[i]) {
pv.eb(k[i], k[i]);
} else {
pv.back().s += k[i];
}
}
int sz = sz(pv);
vpi gap;
f0r(i, sz) {
if (i == 0) {
gap.eb(1, pv[i].f-1);
} else {
gap.eb(pv[i-1].f, pv[i].f-1);
}
if (i == sz-1) {
gap.eb(pv[i].f, n);
}
}
int num = sz(gap);
vi taken(num);
f0r(i, sz) {
int need = pv[i].s;
int val = pv[i].f;
f0r(i, num) {
auto& x = gap[i];
if (x.f < val) continue;
int rem = query(ti[val], x.f, x.s, 1, n);
rem -= taken[i];
if (rem >= need) {
taken[i] += need;
need = 0;
} else {
need -= rem;
taken[i] += rem;
}
if (need == 0) break;
}
if (need) return 0;
}
return 1;
}
