#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
const int INF=0x3f3f3f3f;
const int MAXN=5e5+5;
struct Node{
int val;
Node *l, *r;
Node(int val_=0, Node *l_=NULL, Node *r_=NULL) {
val=val_; l=l_; r=r_;
}
};
int n, OFF=1;
pii p[MAXN];
int zad[MAXN], que[MAXN];
Node *T[MAXN];
vector <pii> v;
int dp[MAXN];
Node* build(int d) {
if (d==0) return NULL;
Node *ret=new Node(0, build(d/2), build(d/2));
return ret;
}
Node* update(int ind, int x, Node* pos, int lo, int hi) {
Node *ret=new Node(pos->val+x, pos->l, pos->r);
if (lo==hi-1) return ret;
int mid=(lo+hi)/2;
if (ind<mid) ret->l=update(ind, x, pos->l, lo, mid);
else ret->r=update(ind, x, pos->r, mid, hi);
return ret;
}
int query(Node *lef, Node *rig, int a, int b, int lo, int hi) {
if (lo>=b || hi<=a) return 0;
if (lo>=a && hi<=b) return rig->val-lef->val;
int mid=(lo+hi)/2;
return query(lef->l, rig->l, a, b, lo, mid)+query(lef->r, rig->r, a, b, mid, hi);
}
int nadji(Node *lef, Node *rig, int x, int lo, int hi) {
if (lo==hi-1) return lo;
int mid=(lo+hi)/2;
int des=rig->r->val-lef->r->val;
if (des>=x) return nadji(lef->r, rig->r, x, mid, hi);
return nadji(lef->l, rig->l, x-des, lo, mid);
}
#define DEBUG 0
void init(int N, int A[], int B[]) {
n=N;
for (int i=1; i<=n; ++i) p[i]=mp(A[i-1], B[i-1]);
sort(p+1, p+n+1);
while (OFF<n) OFF*=2;
T[0]=build(OFF);
for (int i=1; i<=n; ++i) {
zad[p[i].X]=i;
T[i]=update(p[i].Y, 1, T[i-1], 0, OFF);
// printf("tournament: %d, updejtam broj %d\n", i, p[i].Y);
}
for (int i=1; i<=n; ++i) if (!zad[i]) zad[i]=zad[i-1];
}
int can(int M, int K[]) {
sort(K, K+M);
for (int i=0; i<M; ++i) que[i+1]=K[i];
v.clear();
que[0]=0;
dp[0]=0;
v.pb(mp(0, M+2));
for (int i=1; i<=M; ++i) {
while (v.size() && v.back().Y<=i) v.pop_back();
assert(!v.empty());
dp[i]=dp[v.back().X]+query(T[zad[que[v.back().X]]], T[zad[que[i]]], que[i], n+1, 0, OFF)-que[i];
#if DEBUG
printf("i: %d, que: %d, dp: %d, prijelaz: %d\n", i, que[i], dp[i], v.back().X);
#endif // DEBUG
if (dp[i]<0) return 0;
while (v.size() && dp[v.back().X]>dp[i]) v.pop_back();
int br=dp[i]-dp[v.back().X];
int lo=i, hi=M, mid;
while (lo<hi) {
mid=(lo+hi+1)/2;
int val_i=dp[i]+query(T[zad[que[i]]], T[zad[que[mid]]], que[mid], n+1, 0, OFF);
int val_j=dp[v.back().X]+query(T[zad[que[v.back().X]]], T[zad[que[mid]]], que[mid], n+1, 0, OFF);
if (val_i<val_j) lo=mid;
else hi=mid-1;
}
#if DEBUG
printf("i: %d, prosli: %d, granica: %d\n", i, v.back().X, lo+1);
#endif // DEBUG
v.pb(mp(i, hi+1));
// dp[i]=INF;
// for (int j=0; j<i; ++j) {
// dp[i]=min(dp[i], dp[j]+query(T[zad[que[j]]], T[zad[que[i]]], que[i], n+1, 0, OFF)-que[i]);
// }
// if (dp[i]<0) return 0;
}
return 1;
}
