#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=6*1e5+5;
vector<long long> t[4*maxn];
long long n;
void update(long long i,long long l,long long r,long long id,long long vl)
{
if(l==r)
{
t[i].push_back(vl);
return;
}
long long m=(l+r)/2;
if(id<=m)update(i*2,l,m,id,vl);
else update(i*2+1,m+1,r,id,vl);
}
void trans(long long i,long long l,long long r)
{
if(l==r)
{
sort(t[i].begin(),t[i].end());
return;
}
long long m=(l+r)/2;
trans(i*2,l,m);
trans(i*2+1,m+1,r);
long long i1=0,i2=0;
while(i1<t[i*2].size()||i2<t[i*2+1].size())
{
if(i1==t[i*2].size())t[i].push_back(t[i*2+1][i2++]);
else if(i2==t[i*2+1].size()||t[i*2][i1]<t[i*2+1][i2])t[i].push_back(t[i*2][i1++]);
else t[i].push_back(t[i*2+1][i2++]);
}
}
long long query(long long i,long long l,long long r,long long ql,long long qr,long long qid)
{
//cout<<l<<" - "<<r<<endl;
if(ql>qr)return 0;
if(ql<=l&&r<=qr)
{
if(t[i].size()==0)return 0;
if(t[i][0]>=qid)return t[i].size();
if(t[i][t[i].size()-1]<qid)return 0;
long long id=t[i].size();
long long lf=0,rt=t[i].size()-1;
while(lf<=rt)
{
long long m=(lf+rt)/2;
//cout<<"? "<<m<<" "<<lf<<" "<<rt<<endl;
if(m>=t[i].size())
{
for(long long j=0;j<1e9;j++);
}
if(t[i][m]>=qid)
{
rt=m-1;
id=m;
}
else lf=m+1;
}
/*for(long long j=0;j<t[i].size();j++)
cout<<t[i][j]<<" ";
cout<<endl;
cout<<id<<" "<<qid<<" +"<<endl;*/
return t[i].size()-id;
}
long long m=(l+r)/2;
return query(i*2,l,m,ql,min(qr,m),qid)+query(i*2+1,m+1,r,max(m+1,ql),qr,qid);
}
void init(int N, int A[], int B[])
{
n=N;
for(long long i=0;i<N;i++)
update(1,1,n,A[i],B[i]);
trans(1,1,n);
//fprlong longf(_outputFile,"%d ", t.query(0,1,maxn,1,3,3,5));
}
long long dp[500005];
int can(int M, int k[])
{
sort(k,k+M);
long long answer=0;
stack<pair<long long,long long> > s;
for(long long i=0;i<M;i++)
{
while(s.size()&&s.top().second==i)s.pop();
long long v1=query(1,1,n,1,k[i],k[i])-k[i];
//fprlong longf(_outputFile,"%d ", v1);
if(s.size()==0/*||dp[s.top().first]>=v1*/)
{
dp[i]=v1;
s.push({i,M});
answer=min(answer,dp[i]);
continue;
}
long long j=s.top().first;
dp[i]=dp[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i];
if(dp[i]>v1)
{
dp[i]=v1;
while(s.size())s.pop();
s.push({i,M});
answer=min(answer,dp[i]);
continue;
}
long long ans=M;
long long l=i+1,r=M-1;
while(l<=r)
{
long long m=(l+r)/2;
if(dp[i]+query(1,1,n,k[i]+1,k[m],k[m])>=dp[j]+query(1,1,n,k[j]+1,k[m],k[m]))
{
ans=m;
r=m-1;
}
else l=m+1;
}
answer=min(answer,dp[i]);
s.push({i,ans});
}
/*for(long long i=0;i<M;i++)
{
fprlong longf(_outputFile,"%d ", dp[i]);
}*/
if(answer<0)return 0;
return 1;
}
/*long long main()
{
cin>>n;
for(long long i=1;i<=n;i++)
{
long long x,y;
cin>>x>>y;
update(1,1,10,x,y);
}
trans(1,1,10);
cout<<"done"<<endl;
long long q;
cin>>q;
for(long long i=1;i<=q;i++)
{
long long x,y,xx,yy;
cin>>x>>y>>xx>>yy;
cout<<query(1,1,10,x,y,xx)<<endl;
}
return 0;
}*/
