#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int n, d[N][N], adj[N][N];
pair<int, int> opt[N];
void findLocation(int N_, int first, int pos[], int t[])
{
memset(adj, -1, sizeof adj);
n=N_;
for (int i=0; i<n; ++i){
pos[i]=-1;
for (int j=i+1; j<n; ++j) d[i][j]=d[j][i]=getDistance(i, j);
}
pos[0]=first;
t[0]=1;
for (int i=0; i<n; ++i){
opt[i]={(int)1e9, (int)1e9};
for (int j=0; j<n; ++j) if (i!=j){
opt[i]=min(opt[i], {d[i][j], j});
}
}
int ir=opt[0].second, il=opt[ir].second;
pos[ir]=pos[0]+opt[0].first; pos[il]=pos[ir]-opt[ir].first; t[il]=1; t[ir]=2;
vector<int> vl, vr;
for (int i=0; i<n; ++i) if (i!=ir && i!=il){
if (d[il][i]>d[ir][i]){
vl.push_back(i);
}else{
vr.push_back(i);
}
}
while ((int)vr.size()){
pair<int, int> mn={(int)1e9, (int)1e9};
for (int i:vr) mn=min(mn, {d[i][ir], i});
int id=mn.second;
pos[id]=pos[ir]+mn.first-opt[ir].first*2; t[id]=2;
for (int i=0; i<n; ++i) if (opt[i].second==id){
pos[i]=pos[id]-opt[i].first;
t[id]=1;
}
ir=id;
vr.erase(find(vr.begin(), vr.end(), id));
}
while ((int)vl.size()){
pair<int, int> mn={(int)1e9, (int)1e9};
for (int i:vl) mn=min(mn, {d[i][il], i});
int id=mn.second;
pos[id]=pos[il]-mn.first+opt[il].first*2; t[id]=1;
for (int i=0; i<n; ++i) if (opt[i].second==id){
pos[i]=pos[id]+opt[i].first;
t[id]=2;
}
il=id;
vl.erase(find(vl.begin(), vl.end(), id));
}
}
