#include <bits/stdc++.h>
#include "rail.h"
const int C = 1;
const int D = 2;
const int M = 1e6 + 5;
using namespace std;
void findLocation(int n, int first, int location[], int stype[]) {
for (int i = 0; i < n; i++) {
stype[i] = 0;
}
vector<int> rev(M, -1);
location[0] = first;
stype[0] = C;
rev[first] = 0;
vector<vector<int>> dist(n, vector<int>(n, 0));
vector<int> order(n - 1);
for (int i = 1; i < n; i++) {
dist[i][0] = dist[0][i] = getDistance(0, i);
order[i - 1] = i;
}
sort(order.begin(), order.end(), [&](const int& a, const int& b) {
return dist[0][a] < dist[0][b];
});
int c = order[0];
location[c] = first + dist[0][c];
stype[c] = D;
rev[location[c]] = c;
int j = c;
for (int i = 1; i < n - 1; i++) {
int z = order[i];
dist[c][z] = dist[z][c] = getDistance(c, z);
if (dist[0][c] + dist[c][z] != dist[0][z]) {
dist[j][z] = dist[z][j] = getDistance(j, z);
int k = (dist[0][j] + dist[j][z] - dist[0][z]) >> 1;
int extra = location[j] - k;
extra = rev[extra];
if (extra != -1 && stype[extra] == D) {
location[z] = location[j] - dist[j][z];
stype[z] = C;
} else {
location[z] = location[0] + dist[0][z];
stype[z] = D;
j = z;
}
rev[location[z]] = z;
}
}
int i = 0;
order.clear();
for (int i = 0; i < n; i++) {
if (i != c) {
order.emplace_back(i);
}
}
sort(order.begin(), order.end(), [&](const int& a, const int& b) {
return dist[c][a] < dist[c][b];
});
i = 0;
for (j = 0; j < n - 1; j++) {
int z = order[j];
if (dist[0][z] == dist[0][c] + dist[c][z] && dist[0][c] < dist[c][z]) {
dist[i][z] = dist[z][i] = getDistance(i, z);
int k = (dist[c][i] + dist[i][z] - dist[c][z]) >> 1;
int extra = location[i] + k;
extra = rev[extra];
if (stype[extra] == C) {
location[z] = location[i] + dist[i][z];
stype[z] = D;
} else {
location[z] = location[c] - dist[c][z];
stype[z] = C;
i = z;
}
rev[location[z]] = z;
}
}
for (i = 1; i < n - 1; i++) {
if (stype[i] == 0) {
stype[i] = C;
location[i] = location[c] - dist[c][i];
}
}
return;
}
