#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, m;
pii p[MAXN];
int zad[MAXN], que[MAXN];
Node *T[MAXN];
int dp[MAXN];
set <pii> S, Sind;
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 f(int lo, int hi, int i, int j) {
int 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[j]+query(T[zad[que[j]]], T[zad[que[mid]]], que[mid], n+1, 0, OFF);
if (val_i<val_j) lo=mid;
else hi=mid-1;
}
return lo+1;
}
void izbaci(pii pp) {
// printf("izbacujem %d\n", pp.Y);
S.erase(pp);
auto it=Sind.find(mp(pp.Y, pp.X));
auto pr=it, nx=it; pr--; nx++;
Sind.erase(it);
if (nx==Sind.end()) return;
pii pom=*nx;
// printf("mijenjam granicu na indexu %d iz %d u ", pom.X, pom.Y);
Sind.erase(nx);
S.erase(mp(pom.Y, pom.X));
pom.Y=f(pom.X, m, pom.X, pr->X);
// printf("%d\n", pom.Y);
Sind.insert(pom);
S.insert(mp(pom.Y, pom.X));
}
int can(int M, int K[]) {
m=M;
sort(K, K+M);
for (int i=0; i<M; ++i) que[i+1]=K[i];
S.clear();
Sind.clear();
que[0]=0;
dp[0]=0;
S.insert(mp(M+2, 0));
Sind.insert(mp(0, M+2));
for (int i=1; i<=M; ++i) {
while (S.begin()->X<=i) izbaci(*S.begin());
assert(!S.empty());
dp[i]=dp[Sind.rbegin()->X]+query(T[zad[que[Sind.rbegin()->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], Sind.rbegin()->X);
#endif // DEBUG
if (dp[i]<0) return 0;
// int br=dp[i]-dp[v.back().X];
int curr=f(i, M, i, Sind.rbegin()->X);
#if DEBUG
printf("i: %d, prosli: %d, granica: %d\n", i, Sind.rbegin()->X, curr);
#endif // DEBUG
Sind.insert(mp(i, curr));
S.insert(mp(curr, i));
// 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;
}
