#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
int n;
int dist[5050][5050];
set<int> C,D;
int fi_dis(int a,int b)
{
if(a==b)return 0;
if(dist[a][b])return dist[a][b];
return dist[a][b]=dist[b][a]=getDistance(a,b);
}
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
for(int i=0;i<n;i++)stype[i]=0;
int a=0;
location[a]=first;
stype[a]=1;
C.insert(first);
if(n==1)return ;
int mn=1e9,b=-1;
for(int i=1;i<n;i++)
{
if(fi_dis(0,i)>mn)continue;
mn=fi_dis(0,i);
b=i;
}
location[b]=location[a]+mn;
stype[b]=2;
D.insert(location[b]);
if(n==2)return ;
for(int i=0;i<n;i++)
{
if(i==b)continue;
fi_dis(b,i);
if(fi_dis(b,i)<fi_dis(b,0)&&fi_dis(b,i)==fi_dis(a,i)-fi_dis(a,b))
{
location[i]=location[b]-fi_dis(b,i);
stype[i]=1;
C.insert(location[i]);
}
}
vector<pair<int,int> > vec;
for(int i=0;i<n;i++)
vec.PB({fi_dis(a,i),i});
sort(vec.begin(),vec.end());
int d_right=b,c_left=a;
for(int i=0;i<n;i++)
{
int nw=vec[i].S;
if(stype[nw])continue;
if(dist[a][nw]-dist[a][b]<dist[b][nw])
{
// right side
// assume c type
int dif=fi_dis(d_right,nw);
int new_loca=location[d_right]-dif;
int flip_loca=*D.upper_bound(new_loca);
if(fi_dis(a,nw) == flip_loca - location[a] + flip_loca - new_loca)
{
// c type
location[nw]=new_loca;
stype[nw]=1;
C.insert(location[nw]);
}
else
{
// d type
location[nw]=location[a]+fi_dis(a,nw);
stype[nw]=2;
D.insert(location[nw]);
d_right=nw;
}
}
else
{
// left side
// assume d type
int dif=fi_dis(c_left,nw);
int new_loca=location[c_left]+dif;
int flip_loca=*prev(C.upper_bound(new_loca));
if(fi_dis(b,nw) == location[b] - flip_loca + new_loca - flip_loca)
{
// type d
location[nw]=new_loca;
stype[nw]=2;
D.insert(location[nw]);
}
else
{
// type c
location[nw]=location[b]-fi_dis(b,nw);
stype[nw]=1;
C.insert(location[nw]);
c_left=nw;
}
}
}
return ;
}
// int main()
// {
// return 0;
// }
