#include <bits/stdc++.h>
using namespace std;
#include "rail.h"
void findLocation(int N, int o, int* x, int* t) {
int d[N] {}, byD[N - 1];
map<int, int> g;
t[0] = g[x[0] = o] = 1;
for(int v = 1; v < N; ++v) {
d[v] = getDistance(0, v);
byD[v-1] = v;
}
sort(byD, byD + N - 1, [&](const int &i, const int &j) {
return d[i] < d[j];
});
int c = byD[0], rD = c, lD = c, rC {}, lC {};
t[c] = g[x[c] = o + d[c]] = 2;
for(const int &v : byD) if(v != c) {
int z = getDistance(c, v);
if(z > d[v]) {
int y = getDistance(rD, v);
int exp = x[rD] - x[rC] + (o + d[v]) - x[rC];
if((y == exp || g[x[rD] - y]) && !g[o + d[v]]) x[rD = v] = o + d[v], t[v] = 2;
else x[v] = x[rD] - y , t[v] = 1;
} else {
int y = getDistance(lC, v);
if(!lC) x[lC = v] = x[c] - z, t[v] = 1;
else {
int exp = x[lD] - x[lC] + x[lD] - (x[c] - z);
if((y == exp || g[x[lC] + y]) && !g[x[c] - z]) x[lC = v] = x[c] - z, t[v] = 1;
else x[v] = x[lC] + y, t[v] = 2;
}
}
if(t[v] == 1 && x[v] > x[rC]) rC = v;
if(t[v] == 2 && x[v] < x[lD]) lD = v;
g[x[v]] = t[v];
}
}
