#include "rail.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
int dist[10000];
void findLocation(int N, int first, int location[], int stype[])
{
for(int i=1; i<N; i++)dist[i]=getDistance(0, i);
vector<int> V(N-1);
iota(V.begin(), V.end(), 1);
sort(V.begin(), V.end(), [](int a, int b){return dist[a]<dist[b];});
location[0]=first;
location[V[0]]=first+dist[V[0]];
stype[0]=1;
stype[V[0]]=2;
int L=0, R=V[0];
vector<int> C={location[0]}, D={location[V[0]]};
for(int i=1; i<N-1; i++){
int d1=getDistance(L, V[i]), d2=getDistance(R, V[i]);
int loc=location[L]+d1;
int t=-1;
for(int j:C)if(j>t && j<loc)t=j;
if(loc-t+location[R]-t==d2){
if(loc<first){
if(dist[V[i]]==dist[V[0]]+location[V[0]]-loc){
location[V[i]]=loc;
stype[V[i]]=2;
D.push_back(loc);
}
}
else{
if(loc-first==dist[V[i]]){
location[V[i]]=loc;
stype[V[i]]=2;
D.push_back(loc);
if(loc>location[R])R=V[i];
}
}
}
loc=location[R]-d2;
t=1e9;
for(int j:D)if(j<t && j>loc)t=j;
if(!stype[V[i]]){
assert(t-loc+t-location[L]==d1);
if(loc>first){
assert(t-loc+t-first==dist[V[i]]);
location[V[i]]=loc;
stype[V[i]]=1;
C.push_back(loc);
}
else{
assert(dist[V[0]]+location[V[0]]-loc==dist[V[i]]);
location[V[i]]=loc;
stype[V[i]]=1;
C.push_back(loc);
if(loc<location[L])L=V[i];
}
}
assert(stype[V[i]]);
}
}
