#include"rail.h"
#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;
void findLocation(int n,int first,int location[],int stype[]){
int calls=0;
vector<pair<int,int>>dist0;
vector<int>dist_from_0(n);
for(int i=1;i<n;i++){
dist_from_0[i]=getDistance(0,i);
calls++;
dist0.emplace_back(dist_from_0[i],i);
}
sort(dist0.begin(),dist0.end());
int left=0,right=0;
stype[0]=1;
location[0]=0;
//for(auto i:dist0)
//cout<<i.first<<" "<<i.second<<"\n";
for(auto[dist,i]:dist0){
if(right==0){
right=i;
location[i]=dist;
stype[i]=2;
continue;
}
int dist1=getDistance(dist0[0].second,i);
calls++;
if(dist1+dist0[0].first==dist){ // i is on the left side
dist-=2*dist0[0].first;
if(dist<0){
location[i]=-dist;
stype[i]=1;
continue;
}
if(left==0){
location[i]=-dist;
stype[i]=1;
left=i;
continue;
}
int dist2=getDistance(left,i);
int mid=(location[left]+dist2-dist)/2;
bool is_left=false;
for(int i=0;i<n;i++){
if(location[i]==mid&&stype[i]==1){
is_left=true;
}
}
if(dist2>location[left]&&is_left){
location[i]=location[left]+dist2;
stype[i]=2;
}else{
left=i;
location[i]=-dist;
stype[i]=1;
}
}else{ // i is on the right side
int dist2=getDistance(right,i);
int mid=(location[right]-dist2+dist)/2;
bool is_left=false;
for(int i=0;i<n;i++){
if(location[i]==mid&&stype[i]==2){
is_left=true;
}
}
if(dist2<location[right]&&is_left){
location[i]=location[right]-dist2;
stype[i]=1;
}else{
right=i;
location[i]=dist;
stype[i]=2;
}
}
}
for(int i=0;i<n;i++){
location[i]+=first;
//if(n<20) cout<<stype[i]<<" "<<location[i]<<"\n";
}
//cout<<"limit: "<<3*(n-1)<<" calls: "<<calls<<"\n";
}
