#include "teams.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 5e5 + 5;
int tree[40*N],le_[30*N], ri_[40*N];
int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
set <pii> s;
set <int > s1;
vector <int> v[N];
int merge(int a, int b) {
return a + b;
}
void build(int node, int le, int ri) {
// cout<<le<<" "<<ri<<" "<<node<<endl;
if (le == ri) {
tree[node] = 0;
return ;
}
cur++;
le_[node] = cur;
cur++;
ri_[node] = cur;
int mid = (le + ri) / 2;
build(le_[node],le,mid);
build(ri_[node],mid + 1, ri);
tree[node] = merge(tree[le_[node]], tree[ri_[node]]);
}
void update(int node, int le, int ri, int idx, int val) {
if (le > idx || ri < idx) return ;
if (le == ri) {
tree[cur] = tree[node] + val;
//cout<<cur<<" "<<le<<" "<<ri<<" "<<tree[cur]<<endl;
return ;
}
int mid = (le + ri) / 2;
int x = cur;
cur++;
le_[x] = le_[node];
ri_[x] = ri_[node];
if (idx <= mid) {
le_[x] = cur;
} else ri_[x] = cur;
update(le_[node], le,mid,idx,val);
update(ri_[node], mid + 1, ri, idx,val);
tree[x] = merge(tree[le_[x]], tree[ri_[x]]);
//cout<<x<<" "<<le<<" "<<ri<<" "<<tree[x]<<endl;
}
int getans(int node, int le, int ri, int start, int end) {
if (le > end || ri < start) return 0;
if (le >= start && ri <= end) {
return tree[node];
}
int mid = (le + ri) / 2;
return merge(getans(le_[node],le,mid,start,end), getans(ri_[node],mid + 1,ri,start,end));
}
int F(int lef, int rig) {
// rig === k[rig]
return getans(root[rig],1,n,rig,n) - getans(root[lef],1,n,rig,n);
}
int getidx(int a, int b) {
int le = k[b]+1;
int ri = n;
int ans = 0;
while (le <= ri) {
int mid = (le + ri) / 2;
if (dp[a] - dp[b] < F(k[b],mid) - F(k[a],mid)) {
ans = mid; ri = mid - 1;
} else le = mid + 1;
}
return ans;
}
void del(int idx) {
// cout<<idx<<" del"<<endl;
if (!s1.count(idx)) return ;
s1.erase(idx);
if (!s1.size()) return ;
int prit = -1, nxt = -1;
if (*s1.begin() < idx) {
prit = *(--s1.upper_bound(idx));
}
if (s1.upper_bound(idx) != s1.end()) nxt = *(s1.upper_bound(idx));
int xx;
if (nxt != -1) {
xx = getidx(idx,nxt);
if (xx) s.erase({xx,nxt});
}
if (prit != -1) {
xx = getidx(prit, idx);
if (xx) s.erase({xx,idx});
if (nxt != -1) {
xx = getidx(prit,nxt);
if (xx)
s.insert({xx,nxt});
}
}
}
void add(int idx) {
//cout<<idx<<" add"<<endl;
s1.insert(idx);
if (!s1.size()) return ;
int prit = -1, nxt = -1;
int xx;
if (*s1.begin() < idx) {
prit = *(--s1.lower_bound(idx));
}
if (s1.upper_bound(idx) != s1.end()) {
nxt = *s1.upper_bound(idx);
}
//cout<<prit<<" "<<nxt<<endl;
if (prit != -1 && nxt != -1) {
xx = getidx(prit, nxt);
if (xx) s.erase({xx,nxt});
}
if (prit != -1) {
xx = getidx(prit,idx);
if (xx) s.insert({xx,idx});//;, cout<<"add "<<xx<<" "<<prit<<" "<<idx<<endl;
}
if (nxt != -1) {
xx = getidx(idx, nxt);
if (xx) s.insert({xx,nxt});//, cout<<"add "<<xx<<" "<<nxt<<endl;
}
}
int can(int M, int K[]) {
s.clear();
s1.clear();
m = M;
for (int i = 1; i <= m; i++) {
dp[i] = 0;
k[i] = K[i - 1];
}
int sum = 0;
for (int i = 1; i <= m; i++) {
sum += k[i];
}
if (sum > n) {
return 0;
}
sort(k + 1, k + m + 1);
dp[0] = 0;
add(0);
for (int i = 1; i <= m; i++) dp[i] = 1e9;
for (int i = 1; i <= m; i++) {
// rodis waishleba index
while (s.size()) {
multiset < pii > :: iterator it = s.begin();
if ((*it).f <= k[i]) {
int todel = (*it).s;
del(todel);
}
else break;
}
int id = *(--s1.end());
dp[i] = dp[id] + F(k[id],k[i]) - k[i];
//cout<<i<<" "<<id<<" "<<dp[i]<<endl;
if (dp[i] < 0) return 0;
add(i);
/*
for (int j = i - 1; j >= 0; j--) {
// k[j]+1 -----> k[i] shualedshi >= k[i]
cnt = getans(root[k[i]],1,n,k[i],n) - getans(root[k[j]],1,n,k[i],n);
dp[i] = min(dp[i],dp[j] + cnt - k[i]);
// cout<<i<<" "<<j<<" "<<dp[j]<<" "<<cnt<<endl;
//cout<<i<<" "<<dp[i]<<endl;
if (dp[i] < 0) {
return 0;
}
}*/
//cout<<i<<" "<<dp[i]<<endl;
}
return 1;
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; i++) {
a[i] = A[i - 1]; b[i] = B[i - 1];
v[a[i]].pb(b[i]);
}
cur = 1; root[0] = 1;
build(1,1,n);
for (int i = 1; i <= n; i++) {
prevroot = root[i - 1];
root[i] = root[i - 1];
for (int j = 0; j < v[i].size(); j++) {
cur++;
root[i] = cur;
update(prevroot, 1,n,v[i][j],1);
prevroot = root[i];
}
}
dp[0] = 0;
}
