#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const long long maxn=6*1e5+5;
vector<long long> t[8*maxn];
long long n;
//static FILE *_inputFile, *_outputFile;
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 maxi;
int num;
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(num==135)
{
int cnt=0;
for(int j=0;j<t[i].size();j++)
if(t[i][j]>=qid)cnt++;
return cnt;
}*/
int id=t[i].size();
maxi=max(maxi,i);
int l1=0,r1=t[i].size()-1;
while(l1<=r1)
{
int m1=(l1+r1)/2;
/*if(m1>t[i].size())
{
//fprintf(_outputFile, "%d ", m1);
//return 0;
}*/
if(t[i][m1]>=qid)
{
id=m1;
r1=m1-1;
}
else l1=m1+1;
}
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);
}
int a[500001],b[500001];
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]);
a[i]=A[i],b[i]=B[i];
}
trans(1,1,n);
//fprlong longf(_outputFile,"%d ", t.query(0,1,maxn,1,3,3,5));
}
long long dp[500005];
long long dp1[500005];
int qquery(int i,int l,int r,int ql,int qr,int qid)
{
int cnt=0;
for(int j=0; j<n; j++)
if(ql<=a[j]&&a[j]<=qr&&b[j]>=qid)cnt++;
return cnt;
}
int can(int M, int k[])
{
num++;
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];
//if(num==135&&i)fprintf(_outputFile, "%d \n", dp[i-1]);
//fprlong longf(_outputFile,"%d ", v1);
if(s.size()==0/*||dp[s.top().first]>=v1*/)
{
//if(num==135)fprintf(_outputFile, "%d \n", -1);
dp[i]=v1;
s.push({i,M});
answer=min(answer,dp[i]);
continue;
}
long long j=s.top().first;
dp[i]=min(v1,dp[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i]);
answer=min(answer,dp[i]);
while(1)
{
if(s.size()==0)
{
s.push({i,M});
break;
}
long long ans=M;
j=s.top().first;
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;
}
if(ans>s.top().second)s.pop();
else
{
s.push({i,ans});
//if(num==135)fprintf(_outputFile,"%d \n", ans);
break;
}
}
}
/*if(num==135)
for(int i=0; i<M; i++)
{
dp1[i]=query(1,1,n,1,k[i],k[i])-k[i];
for(int j=0; j<i; j++)
{
dp1[i]=min(dp1[i],dp1[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i]);
fprintf(_outputFile,"%d ", dp1[j]+query(1,1,n,k[j]+1,k[i],k[i])-k[i]);
}
fprintf(_outputFile,"%d\n",dp1[i]);
}
/*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;
}*/
/*
21 1 3 4 4 6 10 10 10 30 40 90 546 819 2460 3280 4100 5740 14762 22143 29524 44286 44286
21 1 3 7 8 20 30 40 90 91 91 91 273 455 819 820 1640 2460 4920 4920 29524 66429 66429
21 5 6 8 30 30 60 80 91 182 364 364 546 820 820 820 2460 3280 7380 14762 36905 36905 36905
19 4 5 8 40 50 80 182 637 637 820 3280 4920 6560 7381 7381 7381 22143 36905 66429 66429
22 1 4 6 9 10 10 10 30 40 90 91 364 546 728 820 1640 3280 7380 14762 14762 36905 44286 44286
22 1 4 5 7 10 10 10 30 50 90 91 364 546 819 820 3280 4920 5740 7381 36905 44286 51667 51667
19 3 4 8 60 90 273 273 455 455 820 820 820 2460 3280 7380 14762 29524 36905 66429 66429
18 2 6 8 20 30 40 90 455 637 637 5740 7380 7381 7381 7381 22143 36905 66429 66429
20 2 4 6 8 40 60 70 455 728 820 820 2460 4920 6560 7381 7381 7381 22143 29524 66429 66429
20 1 1 1 3 5 9 10 50 50 80 91 455 819 1640 1640 4100 4100 36905 44286 59048 59048
19 2 4 8 40 50 70 273 364 364 455 3280 4920 5740 7381 7381 7381 22143 36905 66429 66429
21 2 6 9 10 10 10 30 40 90 182 546 819 820 820 2460 2460 3280 5740 36905 36905 36905 36905
17 1 7 9 10 10 10 30 40 90 455 546 637 4920 5740 22143 44286 44286 44286
*/
