#include "rail.h"
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
using namespace std;
int dis[5005][5005];
int gdis(int i, int j)
{
if(dis[i][j]==-1) dis[i][j]=getDistance(i, j);
return dis[i][j];
}
void findLocation(int n, int first, int location[], int stype[])
{
memset(dis, -1, sizeof(dis));
vector<pii>d0;
for(int i=1; i<n; i++)
{
d0.pb({gdis(0, i), i});
}
sort(all(d0));
int l=0, r=d0[0].S;
stype[0]=1;
location[0]=first;
stype[d0[0].S]=2;
location[d0[0].S]=first+d0[0].F;
for(int i=1; i<n-1; i++)
{
int k=d0[i].S;
bool f=0;
if(gdis(l, k)>gdis(r, k)) f=1;
for(int e=0; e<n; e++)
{
if(e!=l and e!=k and gdis(l, e)+gdis(e, k)==gdis(l, k))
{
f=1;
break;
}
}
for(int e=0; e<n; e++)
{
if(e!=r and e!=k and gdis(r, e)+gdis(e, k)==gdis(r, k))
{
f=0;
break;
}
}
if(f)
{
stype[k]=1;
location[k]=location[r]-gdis(r, k);
if(location[k]<location[l]) l=k;
}
else
{
stype[k]=2;
location[k]=location[l]+gdis(l, k);
if(location[k]>location[r]) r=k;
}
}
}
