#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
int d[N],d2[N],mn=1e9,l=0,r=-1;
location[0]=first;
stype[0]=1;
for (int i=1;i<N;i++){
d[i]=getDistance(0,i);
if (d[i]<mn){
mn=d[i];
r=i;
}
}
location[r]=first+mn;
stype[r]=2;
d2[0]=mn;
vector <pair <int, int>> vl,vr;
for (int i=1;i<N;i++)
if (i!=r){
d2[i]=getDistance(r,i);
if (d2[i]<d2[0]){
location[i]=location[r]-d2[i];
stype[i]=1;
}
else{
if (d2[i]<d[i])
vl.emplace_back(d2[i],i);
else
vr.emplace_back(d[i],i);
}
if (d2[i]<mn){
mn=d2[i];
l=i;
}
}
sort(vl.begin(),vl.end());
sort(vr.begin(),vr.end());
int last=0;
for (auto [dist,i]:vl){
int val=getDistance(last,i);
if (val>d2[last]){
location[i]=location[r]-d2[i];
stype[i]=1;
last=i;
continue;
}
location[i]=location[last]+val;
stype[i]=2;
}
last=r;
int diff=location[l]-first;
for (auto [dist,i]:vr){
int val=getDistance(last,i);
if (val>d[last]-diff){
location[i]=location[0]+d[i];
stype[i]=2;
last=i;
continue;
}
location[i]=location[last]-val;
stype[i]=1;
}
}
