#include "rail.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
if (N == 1)return;
vector< pair<int,int> >v;
for (int i = 1;i<N;i++) {
int ret = getDistance(0 , i);
v.push_back({ret , i});
}
sort(v.begin(),v.end());
int C = 0 , D = (*v.begin()).S;
location[D] = first + (*v.begin()).F;
stype[D] = 2;
set<int>lft , rgt;
lft.insert(-location[C]);
rgt.insert(location[D]);
N--;
for (int i = 1;i<N;i++) {
int c = v[i].S;
int ret1 = getDistance(c , C);
int ret2 = getDistance(c , D);
int pos = location[D] - ret2;
auto it = rgt.lower_bound(pos);
if (abs(*it - location[C]) + abs(*it - pos) == ret1) {
location[c] = location[D] - ret2;
stype[c] = 1;
if (location[c] < location[C])C = c;
lft.insert(-location[c]);
continue;
}
pos = location[C] + ret1;
it = lft.lower_bound(-pos);
if (abs(*it + location[D]) + abs(*it + pos) == ret2) {
location[c] = location[C] + ret1;
stype[c] = 2;
if (location[c] > location[D])D = c;
rgt.insert(location[c]);
continue;
}
}
}
