#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++){
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;
int lowest = 0;
vector<int> v;
v.push_back(0);
for(int i = 1;i<ord0.size();i++){
if(get(0,ord0[i]) != get(posD,ord0[i]) + get(0,posD))continue;
if(get(posD,ord0[i]) < get(0,posD)){
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - get(posD,ord0[i]);
continue;
}
int candpos = location[lowest] + get(lowest,ord0[i]);
if(candpos >= location[0]){
lowest = ord0[i];
v.push_back(ord0[i]);
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - get(posD,ord0[i]);
continue;
}
int closest = -1;
for(auto u:v){
if(location[u] < candpos){
if(closest == -1 || location[closest] < location[u]){
closest = u;
}
}
}
assert(closest != -1);
if(get(posD,ord0[i]) != get(posD,closest) + get(closest,ord0[i])){
lowest = ord0[i];
v.push_back(ord0[i]);
stype[ord0[i]] = 1;
location[ord0[i]] = location[posD] - get(posD,ord0[i]);
}
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;
// }
// }
vector<int> ordD;
for(int i = 0;i<n;i++){
if(i != posD){
ordD.push_back(i);
}
}
sort(ordD.begin(),ordD.end(),[&](int a,int b){
return get(posD,a) < get(posD,b);
});
v.clear();
v.push_back(posD);
int highest = posD;
return;
for(int i = 1;i<ordD.size();i++){
if(get(posD,ordD[i]) != get(0,ordD[i]) + get(0,posD))continue;
assert(stype[ordD[i]] == 0);
int candpos = location[highest] - get(highest,ordD[i]);
if(candpos <= location[posD]){
highest = ordD[i];
v.push_back(ordD[i]);
stype[ordD[i]] = 2;
location[ordD[i]] = location[0] + get(0,ordD[i]);
continue;
}
int closest = -1;
for(auto u:v){
if(location[u] > candpos){
if(closest == -1 || location[closest] > location[u]){
closest = u;
}
}
}
assert(closest != -1);
if(get(0,ordD[i]) != get(0,closest) + get(closest,ordD[i])){
highest = ordD[i];
v.push_back(ordD[i]);
stype[ordD[i]] = 2;
location[ordD[i]] = location[0] + get(0,ordD[i]);
}
else{
stype[ordD[i]] = 1;
location[ordD[i]] = candpos;
}
}
// for(int i = 0;i<n;i++){
// if(stype[i]){
// cout << i << endl;
// cout << stype[i] << ' ' << location[i] << endl;
// }
// }
}
