#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void findLocation(int N, int first, int location[], int stype[]) {
vector<int> dist0(N), dista(N), distl(N), distr(N);
stype[0] = 1;
location[0] = first;
vector<int> left, right;
int a = -1;
for (int x = 1; x < N; x++) {
dist0[x] = getDistance(0, x);
if (a == -1 || dist0[x] < dist0[a]) {
a = x;
}
}
int b = dist0[a] + first, c = -1;
stype[a] = 2;
location[a] = b;
for (int x = 0; x < N; x++) {
if (x == a) {
continue;
}
dista[x] = getDistance(a, x);
if (c == -1 || dista[x] < dista[c]) {
c = x;
}
}
int d = b - dista[c];
stype[c] = 1;
location[c] = d;
for (int x = 0; x < N; x++) {
if (x == 0 || x == a) {
continue;
}
if (dista[x] < dist0[a]) {
stype[x] = 1;
location[x] = dista[x] + b;
} else if (dista[x] < dist0[x]) {
// left
left.pb(x);
} else {
// right
right.pb(x);
}
}
sort(left.begin(), left.end(), [dista](const auto &lhs, const auto &rhs) {
return dista[lhs] < dista[rhs];
});
sort(right.begin(), right.end(), [dista](const auto &lhs, const auto &rhs) {
return dista[lhs] < dista[rhs];
});
if (!left.empty()) {
// handle left side
int closestUp = a;
for (int i = 1; i < (int)left.size(); i++) {
distl[left[i]] = getDistance(left[0], left[i]);
}
stype[left[0]] = 1;
location[left[0]] = b - dista[left[0]];
while (1) {
vector<int> to_erase;
for (int i = 1; i < (int)left.size(); i++) {
if (dista[left[i]] == dista[left[0]] + distl[left[i]]) {
// to the right of left[0]
stype[left[i]] = 2;
location[left[i]] = distl[left[i]] + location[left[0]];
if (location[closestUp] > location[left[i]]) {
closestUp = left[i];
}
to_erase.pb(i);
}
}
vector<int> new_left;
for (int i = 1; i < (int)left.size(); i++) {
if (!binary_search(to_erase.begin(), to_erase.end(), i)) {
new_left.pb(left[i]);
}
}
if (new_left.empty()) {
break;
}
stype[new_left[0]] = 1;
location[new_left[0]] = b - dista[new_left[0]];
for (int i = 1; i < (int)new_left.size(); i++) {
distl[i] -= closestUp - location[left[0]] + closestUp - location[new_left[0]];
}
left = new_left;
}
}
if (!right.empty()) {
// handle right side
int closestDown = c;
for (int i = 1; i < (int)right.size(); i++) {
distr[right[i]] = getDistance(right[0], right[i]);
}
stype[right[0]] = 2;
location[right[0]] = b + dista[right[0]] - 2 * (b - d);
while (1) {
vector<int> to_erase;
for (int i = 1; i < (int)right.size(); i++) {
if (dista[right[i]] == dista[right[0]] + distr[right[i]]) {
// to the left of right[0]
stype[right[i]] = 1;
location[right[i]] = location[right[0]] - distr[right[i]];
if (location[closestDown] < location[right[i]]) {
closestDown = right[i];
}
to_erase.pb(i);
}
}
vector<int> new_right;
for (int i = 1; i < (int)right.size(); i++) {
if (!binary_search(to_erase.begin(), to_erase.end(), i)) {
new_right.pb(right[i]);
}
}
if (new_right.empty()) {
break;
}
stype[new_right[0]] = 2;
location[new_right[0]] = b + dista[new_right[0]] - 2 * (b - d);
for (int i = 1; i < (int)new_right.size(); i++) {
distr[i] -= location[right[0]] - closestDown + location[new_right[0]] - closestDown;
}
right = new_right;
}
}
}
