#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int dp[5000][5000];
int tot = 0;
int get(int a,int b){
if(a == b)
return 0;
if(dp[a][b] || dp[b][a])
return max(dp[a][b],dp[b][a]);
tot--;
assert(tot >= 0);
return dp[a][b] = getDistance(a,b);
}
void findLocation(int n, int first, int location[], int stype[]){
tot = n * (n-1)/2;
for(int i = 0;i<n;i++){
stype[i] = 0;
for(int j = 0;j<n;j++){
dp[i][j] = 0;
}
}
location[0] = first;
stype[0] = 1;
if(n == 1)return;
vector<int> ord0;
for(int i = 0;i<n;i++){
if(i != 0){
ord0.push_back(i);
}
}
sort(ord0.begin(),ord0.end(),[&](int a,int b){
return get(0,a) < get(0,b);
});
int posD = ord0[0];
location[posD] = location[0] + get(0,posD);
stype[posD] = 2;
vector<int> v;
v.push_back(0);
for(int i = 0;i<ord0.size();i++){
if(stype[ord0[i]])continue;
if(get(0,ord0[i]) != get(posD,ord0[i]) + get(0,posD))continue;
if(get(0,ord0[i]) < 2 * get(0,posD)){
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - (get(0,ord0[i]) - get(0,posD));
continue;
}
int candpos = location[v.back()] + get(v.back(),ord0[i]);
int closest = -1;
for(auto u:v){
if(location[u] < candpos){
if(closest == -1 || location[closest] < location[u]){
closest = u;
}
}
}
if(closest == 0 || get(0,ord0[i]) != get(0,closest) + (candpos - location[closest])){
v.push_back(ord0[i]);
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - (get(0,ord0[i]) - get(0,posD));
}
else{
stype[ord0[i]] = 2;
location[ord0[i]] = candpos;
}
}
// for(int i = 0;i<n;i++){
// if(stype[i]){
// cout << i << endl;
// cout << stype[i] << ' ' << location[i] << endl;
// }
// }
v.clear();
v.push_back(posD);
for(int i = 0;i<ord0.size();i++){
if(stype[ord0[i]])continue;
int candpos = location[v.back()] - get(v.back(),ord0[i]);
int closest = -1;
for(auto u:v){
if(location[u] > candpos){
if(closest == -1 || location[closest] > location[u]){
closest = u;
}
}
}
if(get(0,ord0[i]) != get(0,closest) + (location[closest] - candpos)){
v.push_back(ord0[i]);
stype[ord0[i]] = 2;
location[ord0[i]] = location[0] + get(0,ord0[i]);
}
else{
stype[ord0[i]] = 1;
location[ord0[i]] = candpos;
}
}
// for(int i = 0;i<n;i++){
// if(stype[i]){
// cout << i << endl;
// cout << stype[i] << ' ' << location[i] << endl;
// }
// }
}
