#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5000 + 10;
ll dist[MAXN];
int ind[MAXN];
void findLocation(int N, int first, int location[], int stype[])
{
stype[0] = 1;
location[0] = first;
for(int i=1; i<N; i++){
dist[i] = getDistance(0, i);
ind[i] = i;
}
sort(ind, ind+N, [](int fi, int se){return dist[fi] < dist[se];});
int cc = 0, cd = ind[1];
stype[cd] = 2;
location[cd] = first + dist[cd];
for(int i=2; i<N; i++){
int ci = ind[i];
ll distc = getDistance(cc, ci);
ll distd = getDistance(cd, ci);
if(distc > distd){
stype[ci] = 1;
location[ci] = location[cd] - distd;
if(distd > location[cd] - location[cc])
cc = ci;
} else {
stype[ci] = 2;
location[ci] = location[cc] + distc;
if(distc > location[cd] - location[cc])
cd = ci;
}
}
}
