#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 5005;
ll dist[N][N];
ll D_(ll i, ll j){
if(i == j) return 0;
if(dist[i][j] != -1) return dist[i][j];
dist[i][j] = dist[j][i] = getDistance(i, j);
return dist[i][j];
}
void findLocation(int n, int first, int location[], int stype[]){
memset(dist, -1, sizeof(dist));
ii mn = {1e9, 0};
location[0] = first; stype[0] = 1;
if(n == 1) return;
vector < ll > all;
set < ii > C,D;
for(ll i = 1; i < n; i++){
all.pb(i);
}
sort(all.begin(), all.end(),[&](ll i, ll j){
return D_(0, i) < D_(0, j);
});
C.in({first, 0});
D.in({first + D_(0, all[0]), all[0]});
ll l = 0, r = all[0];
location[r] = first + D_(l, r);
stype[r] = 2;
for(auto i : all){
if(i == r) continue;
// L i R (C)
ll x = D_(l, i);
ll y = D_(r, i);
ll ex = location[r] - y;
if(ex >= first){
auto [pos, j] = *D.lower_bound({ex, 0} );
if(pos != ex && x == pos - location[l] + pos - ex){
location[i] = ex;
stype[i] = 1; // C
C.in({location[i], i});
continue;
}
}
// L i R (D)
ex = location[l] + x;
if(ex <= first){
auto [pos, j] = *(--C.upper_bound({ex, 1e9}));
if(pos != ex && y == location[r] - pos + ex - pos){
location[i] = ex;
stype[i] = 2; // D
D.in({location[i], i});
continue;
}
}
// L R i
ll ex1 = location[l] + x;
ll ex2 = location[r] - y;
if((ex1 == location[0] + D_(0, i) && ex1 > location[r]) && (ex2 < location[l] && D_(0, i) == 2*location[all[0]] - location[0] - ex2)){
location[i] = ex2;
stype[i] = 1; // C
C.in({location[i], i});
l = i;
}else if(ex1 == location[0] + D_(0, i) && ex1 > location[r]){
location[i] = ex1;
stype[i] = 2; // D
D.in({location[i], i});
r = i;
}else{
location[i] = ex2;
stype[i] = 1; // C
C.in({location[i], i});
l = i;
}
}
return;
}
