#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 m = (dL - dR + location[L] + location[R]) / 2;
if (const auto itr = map.find(m); (itr == map.end() and m > location[0]) or (itr != map.end() and itr->second == 1)) {
location[id] = location[L] + dL;
stype[id] = 2;
if (location[R] < location[id]) {
R = id;
}
} else {
location[id] = location[R] - dR;
stype[id] = 1;
if (location[L] > location[id]) {
L = id;
}
}
map[location[id]] = stype[id];
}
}
