#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,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 (d[i]==d2[i]+d[r])
vl.emplace_back(d2[i],i);
else
vr.emplace_back(d[i],i);
}
sort(vl.begin(),vl.end());
sort(vr.begin(),vr.end());
int last=0;
vector <pair <int, int>> ve;
for (auto [dist,i]:vl){
if (ve.empty()){
location[i]=location[r]-dist;
stype[i]=1;
last=i;
ve.emplace_back(-location[i],i);
continue;
}
int val=getDistance(last,i);
int pos=ve[lower_bound(ve.begin(),ve.end(),make_pair(-location[last]-val,i))-ve.begin()].second;
if ((pos==last?val:getDistance(pos,i))+d2[pos]!=dist){
location[i]=location[r]-dist;
stype[i]=1;
last=i;
ve.emplace_back(-location[i],i);
continue;
}
location[i]=location[last]+val;
stype[i]=2;
}
last=r;
ve.clear();
ve.emplace_back(location[r],r);
for (auto [dist,i]:vr){
int val=getDistance(last,i);
int pos=ve[lower_bound(ve.begin(),ve.end(),make_pair(location[last]-val,i))-ve.begin()].second;
if ((pos==last?val:getDistance(pos,i))+d[pos]!=dist){
location[i]=first+dist;
stype[i]=2;
last=i;
ve.emplace_back(location[i],i);
continue;
}
location[i]=location[last]-val;
stype[i]=1;
}
}
