#include "rail.h"
#include<algorithm>
std::pair<int,int> a[5555];
int c[5555];
int d[5555];
void findLocation(int n,int fir,int loc[],int stp[])
{
int i,j,k,l,sec,le,ri,t;
loc[0]=fir;
stp[0]=1;
fir=0;
for(i=1;i<n;i++)
{
c[i]=getDistance(fir,i);
a[i].first=c[i];
a[i].second=i;
}
sec=std::min_element(a+1,a+n)->second;
loc[sec]=loc[fir]+c[sec];
stp[sec]=2;
for(i=1;i<n;i++)
{
d[i]=getDistance(sec,i);
a[i].first=std::min(c[i],d[i]);
}
std::sort(a+1,a+n);
le=fir;
ri=sec;
for(i=2;i<n;i++)
{
j=a[i].second;
if(c[j]==d[j]+c[sec])
{
t=getDistance(le,j);
l=-1;
for(k=0;k<i;k++)if(stp[a[k].second]==1&&loc[a[k].second]<loc[le]+t&&(l==-1||loc[a[k].second]>loc[l]))l=a[k].second;
if(l>=0&&d[j]==loc[sec]-loc[l]+loc[le]+t-loc[l])
{
loc[j]=loc[le]+t;
stp[j]=2;
}
else
{
loc[j]=loc[sec]-d[j];
stp[j]=1;
if(loc[j]<loc[le])le=j;
}
}
else
{
t=getDistance(ri,j);
l=-1;
for(k=0;k<i;k++)if(stp[a[k].second]==2&&loc[a[k].second]>loc[ri]-t&&(l==-1||loc[a[k].second]<loc[l]))l=a[k].second;
if(l>=0&&c[j]==loc[l]-loc[fir]+loc[l]-loc[ri]+t)
{
loc[j]=loc[ri]-t;
stp[j]=1;
}
else
{
loc[j]=loc[fir]+c[j];
stp[j]=2;
if(loc[j]>loc[ri])ri=j;
}
}
}
}
