#include <bits/stdc++.h>
#define DEBUG true
#include "rail.h"
using namespace std;
const int MAX_N = 5e3 + 10;
const int INF = 1e9 + 7;
int min_dist, firstD, latestC, latestD, flip_pos;
int dist[MAX_N][MAX_N], idx[MAX_N];
set <int> C, D;
int ask(int i, int j) {
if(dist[i][j] != -1) {
return dist[i][j];
}
if(i == j) {
return dist[i][j] = 0;
}
return dist[i][j] = dist[j][i] = getDistance(i, j);
}
void findLocation(int N, int first, int location[], int stype[]) {
for(int i = 0; i < N; i++) {
idx[i] = i;
stype[i] = 0;
for(int j = 0; j < N; j++) {
dist[i][j] = -1;
}
}
location[0] = first;
stype[0] = 1;
min_dist = INF;
for(int i = 1; i < N; i++) {
if(min_dist > ask(0, i)) {
min_dist = ask(0, i);
firstD = i;
}
}
location[firstD] = location[0] + ask(0, firstD);
stype[firstD] = 2;
C.insert(location[0]);
D.insert(location[firstD]);
latestC = 0;
latestD = firstD;
for(int i = 1; i < N; i++) {
if(i != firstD) {
if(ask(firstD, i) < ask(firstD, 0) and ask(0, i) - ask(firstD, 0) == ask(firstD, i)) { // find all C type that locate between 0 and firstD
location[i] = location[firstD] - ask(firstD, i);
stype[i] = 1;
C.insert(location[i]);
}
}
}
sort(idx, idx + N, [&](const int &a, const int &b) {
return ask(0, a) < ask(0, b);
});
for(int i = 0; i < N; i++) {
if(stype[idx[i]] != 0) {
continue;
}
if(ask(0, idx[i]) - ask(0, firstD) < ask(idx[i], firstD)) { // it is on the right of firstD
location[idx[i]] = location[latestD] - ask(idx[i], latestD);
flip_pos = *D.upper_bound(location[idx[i]]);
if(ask(0, idx[i]) == 2 * flip_pos - location[idx[i]] - location[0]) {
stype[idx[i]] = 1;
C.insert(location[idx[i]]);
}
else {
location[idx[i]] = location[0] + ask(0, idx[i]);
stype[idx[i]] = 2;
D.insert(location[idx[i]]);
latestD = idx[i];
}
}
else { // it is on the left of 0
location[idx[i]] = location[latestC] + ask(idx[i], latestC);
flip_pos = *prev(C.upper_bound(location[idx[i]]));
if(ask(firstD, idx[i]) == location[firstD] + location[idx[i]] - 2 * flip_pos) {
stype[idx[i]] = 2;
D.insert(location[idx[i]]);
}
else {
location[idx[i]] = location[firstD] - ask(firstD, idx[i]);
stype[idx[i]] = 1;
C.insert(location[idx[i]]);
latestC = idx[i];
}
}
}
}
