#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5100;
int dist[MAXN], v[MAXN];
int getdistance(int i, int j){
return getDistance(i,j);
}
bool cmp(int i, int j){
return dist[i] < dist[j];
}
map<int, int> ma;
void findLocation(int n, int first, int location[], int stype[])
{
location[0] = first, stype[0] = 1;
if(n == 1) return;
for(int i = 1; i < n; i++){
dist[i] = getdistance(0,i);
v[i] = i;
}
sort(v, v + n, cmp);
int L, R;
L = 0, R = v[1];
location[R] = first + dist[R];
stype[R] = 2;
ma[location[L]] = 1;
ma[location[R]] = 2;
for(int i = 2; i < n; i++){
int x = v[i];
int dL = getdistance(L,x);
int dR = getdistance(R,x);
int mid = (location[L] + dL + location[R] - dR)/2;
if(ma[mid] == 1 || (ma[mid] == 0 && location[0] < mid)){
location[x] = location[L] + dL;
stype[x] = 2;
if(location[x] > location[R]) R= x;
}
else{
location[x] = location[R] - dR;
stype[x] = 1;
if(location[x] < location[L]) L = x;
}
ma[location[x]] = stype[x];
}
return;
}
