#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using Node = array<int, 3>;
int dist[5005][5005];
void findLocation(int N, int first, int location[], int stype[]) {
map<int, int> mp;
stype[0] = 1; location[0] = first; mp[first] = 0;
vector<pair<int, int> > vec;
for(int i=1; i<N; i++) vec.push_back({ getDistance(0, i), i });
sort(vec.begin(), vec.end());
location[vec[0].second] = first + vec[0].first;
stype[vec[0].second] = 2; mp[location[vec[0].second]] = vec[0].second;
int l=0, r=vec[0].second;
for(int i=1; i<N; i++) {
int d1 = getDistance(l, vec[i].second);
int d2 = getDistance(r, vec[i].second);
int tm = (location[l] + location[r] + d1 - d2) / 2;
int type;
if(mp.count(tm)) type = stype[mp[tm]];
else type = (tm > first ? 1 : 2);
if(type == 1) {
location[vec[i].second] = location[l] + d1;
if(location[vec[i].second] > location[r]) r = vec[i].second;
} else {
location[vec[i].second] = location[r] - d2;
if(location[vec[i].second] < location[l]) l = vec[i].second;
}
stype[vec[i].second] = 3 - type;
mp[location[vec[i].second]] = vec[i].second;
}
stype[0] = 1;
}
