#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
int n,all[maxn][maxn];
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
location[0]=first;
stype[0]=1;
if(n==1){
return ;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
all[i][j]=all[j][i]=getDistance(i,j);
}
}
vector<pair<int,int>>v;
for(int i=0;i<n;i++){
v.push_back(make_pair(all[0][i],i));
}
sort(v.begin(),v.end());
for(int i=1;i<n;i++){
int mn=1e7,wh=-1;
int u1=v[i].second;
for(int j=i-1;j>=0;j--){
if(all[u1][v[j].second]<mn){
mn=all[u1][v[j].second];
wh=j;
}
}
int u2=v[wh].second;
stype[u1]=1+(stype[u2]==1);
// cout<<u1<<" "<<u2<<endl;
if(stype[u1]==1){
location[u1]=location[u2]-all[u1][u2];
}else{
location[u1]=location[u2]+all[u1][u2];
}
}
}
