#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int n, int first, int location[], int stype[]){
map<pair<int, int>, int>cache;
auto get = [&] (int i, int j){
if(i == j){
return 0;
}
if(i > j){
swap(i, j);
}
auto it = cache.find(make_pair(i, j));
if(it != cache.end()){
return it->second;
}
return cache[make_pair(i, j)] = getDistance(i, j);
};
int d = stype[0] = 1;
location[0] = first;
for(int i = 2; i < n; i++){
if(get(0, i) < get(0, d)){
d = i;
}
}
if(n == 1){
return;
}
stype[d] = 2;
set<pair<int, int>>C, D;
C.emplace(location[0] = first, 0);
D.emplace(location[d] = first + get(0, d), d);
int lc, rd;
auto check_1 = [&] (int i){
int loc = location[lc] + get(lc, i), nc = (*prev(C.lower_bound(make_pair(loc, -1)))).second;
if(get(i, nc) + location[rd] - location[nc] != get(i, rd)){
return false;
}
D.emplace(location[i] = loc, i);
stype[i] = 2;
return true;
};
auto check_2 = [&] (int i){
C.emplace(location[i] = location[rd] - get(rd, i), i);
stype[i] = 1;
};
vector<int>p(n - 1);
iota(p.begin(), p.end(), 1);
p.erase(find(p.begin(), p.end(), d));
sort(p.begin(), p.end(), [&] (int i, int j){
return get(0, i) < get(0, j);
});
for(int& i : p){
lc = (*C.begin()).second;
rd = (*D.rbegin()).second;
if(!check_1(i)){
check_2(i);
}
}
}
