#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
const int N=5e5+100;
struct
{
int lc,rc;
int sum;
}seg[N*30];
int nfi=0;
int build(int l,int r)
{
int cur=nfi;
seg[cur].sum=0;
nfi++;
if(l==r)
return cur;
int mid=(l+r)/2;
seg[cur].lc=build(l,mid);
seg[cur].rc=build(mid+1,r);
return cur;
}
// node =def= seg[node] is being changed
// l,r are the range of seg[node](current segment)
// x is the index to be update
int update(int node,int l,int r,int x)
{
int cur=nfi;
nfi++;
seg[cur]=seg[node];
if(l==r)
{
seg[cur].sum++;
return cur;
}
int mid=(l+r)/2;
if(x<=mid)
seg[cur].lc=update(seg[cur].lc,l,mid,x);
else
seg[cur].rc=update(seg[cur].rc,mid+1,r,x);
seg[cur].sum=seg[seg[cur].lc].sum+seg[seg[cur].rc].sum;
return cur;
}
int get(int node,int l,int r,int ql,int qr)
{
if(qr<l or r<ql)return 0;
if(ql<=l and r<=qr)
return seg[node].sum;
int mid=(l+r)/2;
if(qr<=mid)
return get(seg[node].lc,l,mid,ql,qr);
else if(mid<ql)
return get(seg[node].rc,mid+1,r,ql,qr);
else
return get(seg[node].lc,l,mid,ql,qr)+get(seg[node].rc,mid+1,r,ql,qr);
}
int n,a[N],b[N],till[N],cup;
vector<int> add[N],rem[N];
void init(int Ng, int A[], int B[])
{
n=Ng;
for(int i=0;i<n;i++)
{
a[i]=A[i];
b[i]=B[i];
add[a[i]].push_back(b[i]);
}
till[0]=build(1,n);
cup=till[0];
for(int i=1;i<=n;i++)
{
for(auto j:add[i])
cup=update(cup,1,n,j);
till[i]=cup;
}
}
int Contains(int l,int r)
{
int ans=get(till[l],1,n,r,n);
return ans;
}
int can(int m, int k[])
{
int sm=0;
for(int i=0;i<m;i++)
{
sm+=k[i];
if(sm>n)
{
//Not Possible
return 0;
}
}
sort(k,k+m);
//Here we write the dp solution
int dp[m];
// dp[0]= (#Number of segments [a,b] such that a<=k[0] and k[0]<=b) - k[0]
dp[0]=Contains(k[0],k[0])-k[0];
int mi=dp[0];
for(int i=1;i<m;i++)
{
dp[i]=Contains(k[i],k[i])-k[i];
for(int j=i-1;j>=0;j--)
{
dp[i]=min(dp[i],dp[j] + Contains(k[i],k[i]) - Contains(k[j],k[i]) - k[i]);
}
mi=min(mi,dp[i]);
}
return (mi>=0);
}
