#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;
vector<vector<int>> dist;
vector<int> truemin;
set<int> idk, ik;
int n, f;
int get(int i, int j) {
if (i == j) return INF;
if (i > j) swap(i, j);
if (dist[i][j] == -1) return dist[i][j] = getDistance(i, j);
else return dist[i][j];
}
int findmin(int x) {
int d = INF, node = -1;
for (auto i : idk) {
if (get(x, i) < d) {
d = get(x, i);
node = i;
}
}
return node;
}
int knowninv(int x) {
int d = INF, node = -1;
for (auto i : ik) {
if (i == x) continue;
if (d > get(x, i)) {
d = get(x, i);
node = i;
}
}
return node;
}
void findLocation(int N, int first, int location[], int stype[]) {
n = N; f = first;
dist.resize(N, vector<int> (N, -1));
location[0] = first; stype[0] = 0;
for (int i = 1; i < n; i++) idk.insert(i);
int cur;
cur = findmin(0);
stype[cur] = 1;
location[cur] = first + get(0, cur);
ik.insert(0);
ik.insert(cur);
idk.erase(cur);
int mn = first, mx = location[cur];
while (!idk.empty()) {
int curinv;
curinv = knowninv(cur);
int close = findmin(cur);
int way, yaw;
if (stype[cur] == 0) {way = 1; yaw = -1;}
else {way = -1; yaw = 1;}
if (get(curinv, close) > get(cur, close)) {
location[close] = location[cur] + get(cur, close)*way;
stype[close] = stype[cur] ^ 1;
}
else {
location[close] = location[curinv] + get(curinv, close)*yaw;
stype[close] = stype[curinv] ^ 1;
}
ik.insert(close);
idk.erase(close);
if (location[cur] > mx || location[cur] < mn) cur = close;
mx = max(mx, location[close]);
mn = min(mn, location[close]);
}
for (int i = 0; i < n; i++) stype[i]++;
}
