#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
int mi=0x3f3f3f3f;
int st[2][55555],d[55555][2],v[2222222],o,oo;
int cmp(int a,int b){
return d[a][0]<d[b][0];
}
void findLocation(int n,int fi,int l[],int s[]){
l[0]=fi;
s[0]=v[l[0]]=1;
if(n==1) return ;
int id=0;
for(int i=1;i<n;i++){
d[i][0]=getDistance(0,i);
if(d[i][0]<mi){
mi=d[i][0];
id=i;
}
}
l[id]=l[0]+mi;
s[id]=2;
v[l[id]]=2;
for(int i=1;i<n;i++){
if(i==id) continue;
d[i][1]=getDistance(i,id);
if(d[i][1]+mi==d[i][0]){
if(d[i][1]<mi){
l[i]=l[id]-d[i][1];
v[l[i]]=s[i]=1;
}else{
st[0][++o]=i;
}
}else{
st[1][++oo]=i;
}
}
sort(st[0]+1,st[0]+o+1,cmp);
sort(st[1]+1,st[1]+oo+1,cmp);
int la=0,now=0;
for(int i=1;i<=o;i++){
now=st[0][i];
int len=(d[la][1]-d[now][1]+getDistance(la,now))/2;
if(v[l[la]+len]==1){
s[now]=2;
l[now]=2*(l[la]+len)+d[now][1]-l[id];
}else{
la=now;
s[now]=1;
l[now]=l[id]-d[now][1];
}
v[l[now]]=s[now];
}
la=id;
for(int i=1;i<=oo;i++){
now=st[1][i];
int len=(d[la][0]-d[now][0]+getDistance(la,now))/2;
if(v[l[la]-len]==2){
s[now]=1;
l[now]=2*(l[la]-len)-d[now][0]-l[0];
}else{
la=now;
s[now]=2;
l[now]=l[0]+d[now][0];
}
v[l[now]]=s[now];
}
}
