#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second
const int sz=1<<20;
struct sgt {
sgt *L, *R;
int s;
sgt() {
L=R=NULL; s=0;
}
sgt* add(int l, int r, int i, int x) {
if (r-l==1) {
sgt* nw = new sgt();
nw->s = s+x;
return nw;
}
int m=(l+r)>>1;
if (i<m) {
if (!L) L=new sgt();
sgt* newleft = L->add(l,m,i,x);
sgt* nw = new sgt();
nw->L = newleft;
nw->R = R;
nw->s = s+x;
return nw;
} else {
if (!R) R=new sgt();
sgt* newright = R->add(m,r,i,x);
sgt* nw = new sgt();
nw->L = L;
nw->R = newright;
nw->s = s+x;
return nw;
}
}
sgt* add(int i, int x) {
return add(0,sz,i,x);
}
int sum(int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return 0;
if (lx<=l && r<=rx) return s;
int m=(l+r)>>1;
int lq = L?L->sum(l,m,lx,rx):0;
int rq = R?R->sum(m,r,lx,rx):0;
return lq+rq;
}
int sum(int l, int r) {
return sum(0,sz,l,r);
}
int get(int i) {
return sum(0,sz,0,i+1);
}
};
sgt* st[(int)5e5+55];
pi a[(int)5e5];
int n;
void init(int _n, int f[], int s[]) {
n=_n;
forn(i,n) a[i]={f[i],s[i]};
vector<vector<int>> v(n+1);
forn(i,n) v[a[i].s].pb(i);
st[0]=new sgt();
forn(i,n) {
st[i+1]=st[i];
for(auto&x:v[i+1]) {
auto t=st[i+1]->add(a[x].f,1);
st[i+1]=t;
}
}
}
int can(int m, int k[]) {
vector<int> v(m);
forn(i,m) v[i]=k[i];
sort(all(v));
int s=0; forn(i,m) s+=k[i];
if (s>n) return 0;
if (m>=343) {
reverse(all(v));
set<pi> q;
vector<vector<int>> add(n+1);
vector<vector<int>> del(n+1);
forn(i,n) add[a[i].s].pb(i), del[a[i].f].pb(i);
int p=0;
for (int i=n; i>0; --i) {
for (auto&x:add[i]) {
q.insert({-a[x].f,x});
}
while (p<m && i==v[p]) {
if (q.size()<i) return 0;
forn(iter,i) {
auto it=q.begin(); q.erase(q.begin());
}
++p;
}
for (auto&x:del[i]) {
if (q.count({-a[x].f,x})) q.erase({-a[x].f,x});
}
}
return p==m;
}
vector<int> dp(m+1,-1e9);
dp[0]=0;
forn(i,m) {
forn(j,i+1) {
int cnt;
if (j==0) {
cnt=st[n]->sum(0,v[i]+1) - st[v[i]-1]->sum(0,v[i]+1);
} else {
cnt=st[n]->sum(v[j-1]+1,v[i]+1) - st[v[i]-1]->sum(v[j-1]+1,v[i]+1);
}
dp[i+1]=max(dp[i+1],dp[j]+v[i]-cnt);
}
if (dp[i+1]>0) return 0;
}
return 1;
}
