#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define oo 1000000000
void findLocation(int n, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
vector<int> d0(n);
for (int i = 1; i < n; ++i) d0[i] = getDistance(0, i);
vector<bool> visited(n); visited[0] = true;
if (n == 1) return;
int mni = -1;
for (int i = 0; i < n; ++i){
if (!visited[i] && (mni == -1 || d0[i] < d0[mni])) mni = i;
}
location[mni] = location[0] + d0[mni];
stype[mni] = 2;
visited[mni] = true;
int l = 0, r = mni;
for (int j = 2; j < n; ++j){
mni = -1;
for (int i = 0; i < n; ++i){
if (!visited[i] && (mni == -1 || d0[i] < d0[mni])) mni = i;
}
int dl = getDistance(l, mni), dr = getDistance(r, mni);
visited[mni] = true;
if (l != 0 && d0[mni] == dl + d0[l]) {
location[mni] = location[l] + dl;
stype[mni] = 2;
} else if (d0[mni] == dr + d0[r]){
location[mni] = location[r] - dr;
stype[mni] = 1;
if (location[mni] < location[l]) l = mni;
} else{
location[mni] = location[0] + d0[mni];
stype[mni] = 2;
r = mni;
}
}
}
