#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
void findLocation(int N, int first, int location[], int stype[])
{
vector<int> dist0(N);
location[0] = first;stype[0] = 1;
for(int i = 1; i <= N; i++){
int here = getDistance(0, i);
stype[i] = 0;
dist0[i] = here;
}
vi pos(N-1), distp(N);
iota(pos.begin(), pos.end(), 1);
sort(pos.begin(), pos.end(), [&](int a, int b){
return dist0[a] < dist0[b];
});
int p = pos[0];
stype[p] = 2;
location[p] = first + dist0[p];
vi left, right;
for(int u : pos){
if(u != p){
distp[u] = getDistance(p, u);
if(dist0[u] == dist0[p] + distp[u]){
if(distp[u] < dist0[p]){
stype[u] = 1;
location[u] = location[p] - distp[u];
}
else
left.pb(u);
}
else right.pb(u);
}
}
vi up;
for(int u : right){
if(up.empty()){
up.pb(u);
stype[u] = 2;
location[u] = location[0] + dist0[u];
continue;
}
int f = getDistance(up.back(), u);
int pos = -1;
for(int u : up){
if(location[u] >= location[up.back()]-f){
pos = u;
break;
}
}
int t = f - (location[up.back()] - location[pos]);
if(dist0[u] == dist0[pos] + t){
stype[u] = 1;
location[u] = location[up.back()] - f;
}
else{
stype[u] = 2;
location[u] = location[0] + dist0[u];
up.pb(u);
}
}
vi down;
for(int u : left){
if(down.empty()){
stype[u] = 1;
location[u] = location[p] - distp[u];
down.pb(u);
continue;
}
int f = getDistance(down.back(), u);
int pos = -1;
for(int u : down){
if(location[u] <= location[down.back()] + f){
pos = u;
break;
}
}
int t = f - (location[pos] - location[down.back()]);
if(distp[u] == distp[pos] + t){
stype[u] = 2;
location[u] = location[down.back()] + f;
}
else{
stype[u] = 1;
location[u] = location[p] - distp[u];
down.pb(u);
}
}
}
