#include "rail.h"
#include <bits/stdc++.h>
using std::vector;
using std::pair;
void findLocation(int N, int first, int location[], int stype[]) {
vector<pair<int, int>> list(N - 1);
for (int i = 1; i < N; ++i) {
list[i - 1] = {getDistance(0, i), i};
}
std::sort(list.begin(), list.end());
location[0] = first;
stype[0] = 1;
int L = 0, R = list[0].second;
location[R] = location[0] + list[0].first;
stype[R] = 2;
std::map<int, int> map;
map[location[L]] = 1;
map[location[R]] = 2;
for (int i = 1; i < N - 1; ++i) {
const auto& [d0, id] = list[i];
const int dL = getDistance(L, id);
const int dR = getDistance(R, id);
const int d = dL - ((dL + dR) - (location[R] - location[L])) / 2;
if (map[location[L] + d] == 1) {
location[id] = location[L] + dL;
stype[id] = 2;
if (location[id] > location[R]) {
R = id;
}
} else {
location[id] = location[R] - dR;
stype[id] = 1;
if (location[id] < location[L]) {
L = id;
}
}
map[location[id]] = stype[id];
}
}
