#include "railroad_c.h"
#include<stdio.h>
#include <stdlib.h>
int C(const void*i, const void*j){return*(const int*)i-*(const int*)j;}
int lb(int*a,int n,int x){
int l=-1,u=n,m;
while(u-l>1)(a[m=l+(u-l)/2]<x)?(l=m):(u=m);
return u;
}
long long plan_roller_coaster(int n, int *s, int *t) {
static int lef[1000000],rgt[1000000], lc[1000000];
/*compress*/
for(int i=0;i<n;++i) lef[2*i]=s[i],lef[2*i+1]=t[i];
qsort(lef,2*n,sizeof*lef,C);
for(int i=0;i<n;++i) s[i]=lb(lef,2*n,s[i]),t[i]=lb(lef,2*n,t[i]),++s[i],++t[i];
/*yes*/
int lo=0,ro=0;
for (int i = 0; i < n; ++i)
if (s[i]<=t[i])
lef[lo] = i, lc[lo++] = s[i];
for (int i = 0; i < n; ++i) {
if (s[i]>t[i]){
if (lb(lc,lo,s[i]-1)-lb(lc,lo,t[i]))
rgt[ro++]=i;
else
lef[lo]=i,lc[lo++]=s[i]=t[i];
}
}
static int diff[1000000];
for(int i=0;i<sizeof diff/sizeof*diff;++i)diff[i]=0;
for (int i=0;i<lo;++i)
++diff[s[lef[i]]],--diff[1+t[lef[i]]];
for(int i=0;i<ro;++i)
--diff[t[rgt[i]]],++diff[1+s[rgt[i]]];
for(int i=1;i<sizeof diff/sizeof*diff;++i){
diff[i]+=diff[i-1];
if(diff[i]>1)return 1;
}
return 0;
}
