#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "teams.h"
/* PERSISTENT SEGMENT TREE FOR 2D SUM QUERIES */
struct PERSISTENTSEGTREE {
static const int MININD = 0;
static const int MAXIND = 1000;
VI val;
VI lft, rgt;
VI roots;
VI layer;
int addnode() {
val.pb(0);
lft.pb(0);
rgt.pb(0);
return val.size()-1;
}
PERSISTENTSEGTREE() {
roots.pb(addnode());
layer.pb(-1e9);
}
void upd(int PREV, int N, int L, int R, int i, int s) {
if (L == R) {
if (PREV == -1) val[N] = s;
else val[N] = val[PREV] + s;
return;
}
int M = (L + R) / 2;
if (i <= M) {
if (!lft[N]) lft[N] = addnode();
upd(lft[PREV], lft[N], L, M, i, s);
rgt[N] = rgt[PREV];
} else {
if (!rgt[N]) rgt[N] = addnode();
upd(rgt[PREV], rgt[N], M+1, R, i, s);
lft[N] = lft[PREV];
}
val[N] = val[lft[N]] + val[rgt[N]];
}
void upd(int time, int ind, int s = +1) {
roots.pb(addnode());
layer.pb(time);
upd(roots[roots.size()-2], roots[roots.size()-1], MININD, MAXIND, ind, s);
}
int get(int N, int L, int R, int l, int r) {
if (l <= L && R <= r) return val[N];
if (R < l || L > r) return 0;
int M = (L + R) / 2;
int sum = 0;
if (lft[N]) sum += get(lft[N], L, M, l, r);
if (rgt[N]) sum += get(rgt[N], M+1, R, l, r);
return sum;
}
int get(int time, int l, int r) {
return get(roots[upper_bound(all(layer), time) - layer.begin()-1], MININD, MAXIND, l, r);
}
};
struct PURS {
PERSISTENTSEGTREE seg;
PURS(){}
PURS(VPI a) {
for (auto&[x, y] : a) swap(x, y);
sort(all(a));
for (auto[x, y] : a) seg.upd(x, y);
}
int get(int minx, int maxx, int miny, int maxy) {
int ret;
if (maxy < miny) ret = 0;
else ret = seg.get(maxx, miny, maxy) - seg.get(minx-1, miny, maxy);
return ret;
}
};
int n;
VPI ranges;
PURS table;
void init(int N, int A[], int B[]) {
n = N;
ranges = VPI(n);
rep(i, n) ranges[i] = {A[i], B[i]};
table = PURS(ranges);
sort(all(ranges));
}
int can(int M, int K[]) {
int m = M;
VI a(m);
rep(i, m) a[i] = K[i];
sort(all(a));
auto solve1 = [&]() {
VI dp(m);
rep(i, m) {
/*dp[i] = table.get(a[i], +1e9, 0, a[i]) - a[i];*/
dp[i] = table.get(a[i], 999, 0, a[i]) - a[i];
rep(j, i) {
/*setmin(dp[i], dp[j] + table.get(a[i], +1e9, a[j]+1, a[i]) - a[i]);*/
setmin(dp[i], dp[j] + table.get(a[i], 999, a[j]+1, a[i]) - a[i]);
}
}
int mn = 2e9;
for (int x : dp) setmin(mn, x);
return mn >= 0;
};
auto solve2 = [&]() {
multiset<int> ms;
int rpt = 0;
for (int cur : a) {
while (rpt != ranges.size() && ranges[rpt].ff <= cur) {
ms.insert(ranges[rpt++].ss);
}
auto it = ms.lower_bound(cur);
while (cur--) {
if (it == ms.end()) return false;
it++;
ms.erase(prev(it));
}
}
return true;
};
return solve1();
/*int ans1 = solve1();*/
/*int ans2 = solve2();*/
/*cout << ans1 << " " << ans2 << "\n";*/
/*if (ans1 != ans2) {*/
/* cout << n << endl;*/
/* rep(i, n) cout << ranges[i].ff << " " << ranges[i].ss << endl;*/
/* cout << m << endl;*/
/* for (int x : a) cout << x << " ";*/
/* cout << endl;*/
/* abort();*/
/*}*/
return -1;
}
