#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
location[0]=first;
stype[0]=1;
if(N==1) return;
vector<int> d0(N), d2(N);
d0[0]=0;
for(int i=1;i<N;i++) d0[i]=getDistance(0,i);
int p2=-1, mn=INT_MAX;
for(int i=1;i<N;i++) if(d0[i]<mn){ mn=d0[i]; p2=i; }
location[p2]=first+mn;
stype[p2]=2;
d2[p2]=0;
for(int i=0;i<N;i++) if(i!=p2) d2[i]=getDistance(p2,i);
int delta = location[p2]-location[0];
vector<int> V1,V2;
for(int i=1;i<N;i++) if(i!=p2){
if(d0[i]>d2[i]) V1.push_back(i); else V2.push_back(i);
}
while(!V1.empty()){
int pt=-1, best=INT_MAX;
for(int x:V1) if(d0[x]<best){ best=d0[x]; pt=x; }
stype[pt]=2;
location[pt]=location[0]+d0[pt];
vector<int> nxt;
for(int x:V1) if(x!=pt){
int dd=getDistance(pt,x);
if(d0[x]==d0[pt]+dd){ stype[x]=1; location[x]=location[0]+d0[pt]-dd; }
else nxt.push_back(x);
}
V1.swap(nxt);
}
while(!V2.empty()){
int pt=-1, best=INT_MAX;
for(int x:V2) if(d2[x]<best){ best=d2[x]; pt=x; }
stype[pt]=1;
location[pt]=location[p2]-d2[pt];
vector<int> nxt;
for(int x:V2) if(x!=pt){
int dd=getDistance(pt,x);
if(d2[x]==d2[pt]+dd){ stype[x]=2; location[x]=location[p2]-d2[pt]+dd; }
else nxt.push_back(x);
}
V2.swap(nxt);
}
}
