#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN=5005,INF=1e9;
int d0[MAXN];
map<int,int>m;
void findLocation(int N, int first, int location[], int stype[])
{
stype[0]=1;location[0]=first;
if(N==1)return;
vector<pair<int,int>>v;
fore(i,1,N){
d0[i]=getDistance(0,i);
v.emplace_back(d0[i],i);
}
sort(ALL(v));
stype[v[0].snd]=2;location[v[0].snd]=first+v[0].fst;
pair<int,int>X={0,location[0]},Y={v[0].snd,location[v[0].snd]};
m[first]=1;m[Y.snd]=2;
v.erase(v.begin());
for(auto[d,Z]:v){
int yz=getDistance(Y.fst,Z),xz=getDistance(X.fst,Z),xy=(Y.snd-X.snd),p=(X.snd+xz+Y.snd-yz)/2,type=m.find(p)==m.end()?(first<p?1:2):m[p];
stype[Z]=(type==1?2:1);
if(stype[Z]==1){
location[Z]=Y.snd-yz;
m[location[Z]]=stype[Z];
if(X.snd>location[Z]){
X={Z,location[Z]};
}
}else{
location[Z]=X.snd+xz;
m[location[Z]]=stype[Z];
if(Y.snd<location[Z]){
Y={Z,location[Z]};
}
}
}
return;
}
/*
* o puede ser:
* ( ( ) )
* X Z p Y
* ( ( ) )
* X p Y Z */
