#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(first, 0);
D.emplace(location[d] = first + get(0, d), d);
int lc, rd;
auto in_c = [&] (int p){
auto it = C.lower_bound(make_pair(p, -1));
return it != C.end() && it->first == p;
};
auto in_d = [&] (int p){
auto it = D.lower_bound(make_pair(p, -1));
return it != D.end() && it->first == p;
};
auto check_1 = [&] (int i){
int loc = location[lc] + get(lc, i), m = (loc + location[rd] - get(rd, i)) >> 1;
if(in_c(m) || (!in_d(m) && location[0] < m)){
D.emplace(location[i] = loc, i);
stype[i] = 2;
return true;
}
return false;
};
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);
sort(p.begin(), p.end(), [&] (int i, int j){
return get(0, i) < get(0, j);
});
p.erase(p.begin());
for(int& i : p){
lc = (*C.begin()).second;
rd = (*D.rbegin()).second;
if(!check_1(i)){
check_2(i);
}
}
}
