#include "rail.h"
#include <iostream>
#include <algorithm>
using namespace std;
long long int tag[10000005],t[100005],n,map[5005][3],l[1000005],r[1000005],lcnt,rcnt;
bool cmp1(int a,int b)
{
return map[a][1]<map[b][1];
}
bool cmp2(int a,int b)
{
return map[a][0]<map[b][0];
}
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
long long int mi=9999999999,ri=0;
for(int i=1;i<n;i++)
{
map[i][0]=getDistance(0,i);
if(map[i][0]<mi)
{
mi=map[i][0];
ri=i;
}
}
location[ri]=first+mi;
location[0]=first;
stype[0]=1;
stype[ri]=2;
//cout<<ri<<endl;
for(int i=1;i<n;i++)
{
if(ri==i || stype[i]!=0)continue;
if(map[ri][0]+map[i][1]==map[i][0])
{
if(map[i][1]<=map[ri][0])
{
location[i]=location[ri]-map[i][1];
stype[i]=1;
continue;
}
lcnt++;
l[lcnt]=i;
}
else
{
rcnt++;
r[rcnt]=i;
}
}
sort(l+1,l+lcnt+1,cmp1);
sort(r+1,r+rcnt+1,cmp2);
//for(int i=1;i<=lcnt;i++)cout<<l[i]<<" ";
//cout<<endl;
//for(int i=1;i<=rcnt;i++)cout<<r[i]<<" ";
//cout<<endl;
int p=0;
for(int i=1;i<=lcnt;i++)
{
if(p==0)
{
p++;
t[p]=l[i];
location[l[i]]=location[ri]-map[l[i]][1];
stype[l[i]]=1;
tag[location[l[i]]]=1;
}
else
{
long long int tmp=getDistance(t[p],l[i]);
long long int datla=(map[t[p]][1]+tmp-map[l[i]][1])/2;
if(tag[location[t[p]]+datla]==1 && location[t[p]]+datla<location[0])
{
location[l[i]]=location[t[p]]+tmp;
stype[l[i]]=2;
tag[location[l[i]]]=2;
}
else
{
p++;
t[p]=l[i];
location[l[i]]=location[ri]-map[l[i]][1];
stype[l[i]]=1;
tag[location[l[i]]]=1;
}
}
}
p=0;
for(int i=1;i<=rcnt;i++)
{
if(p==0)
{
p++;
t[p]=r[i];
location[r[i]]=location[0]+map[r[i]][0];
stype[r[i]]=2;
tag[location[r[i]]]=2;
}
else
{
long long int tmp=getDistance(t[p],r[i]);
long long int datla=(map[t[p]][0]+tmp-map[r[i]][0])/2;
if(r[i]==2222)
{
cout<<p<<" "<<map[t[p]][0]<<" "<<tmp<<" "<<map[r[i]][0]<<endl;
}
if(tag[location[t[p]]-datla]==2 && location[t[p]]-datla>ri)
{
location[r[i]]=location[t[p]]-tmp;
stype[r[i]]=1;
tag[location[l[i]]]=1;
}
else
{
p++;
t[p]=r[i];
location[r[i]]=location[0]+map[r[i]][0];
stype[r[i]]=2;
tag[location[r[i]]]=2;
}
}
}
//for(int i=0;i<n;i++)cout<<location[i]<<" ";
//cout<<endl;
//for(int i=0;i<n;i++)cout<<stype[i]<<" ";
//cout<<endl;
}
