#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#include "rail.h"
int dist0[5005],mval=2e9,mpos,distm[5005];
void findLocation(int n, int f, int location[], int stype[]){
if(n==1){
location[0] = f;
stype[0] = 1;
return;
}
for(int i=1;i<=n-1;i++){
dist0[i] = getDistance(0,i);
if(dist0[i]<mval){
mval = dist0[i];
mpos = i;
}
}
for(int i=0;i<=n-1;i++){
if(i!=mpos){
distm[i] = getDistance(mpos,i);
}
}
location[0] = f;
location[mpos] = f+dist0[mpos];
stype[0] = 1;
stype[mpos] = 2;
vector<pair<int,int>> lef,rit;
for(int i=1;i<=n-1;i++){
if(i!=mpos){
if(distm[i]<=dist0[mpos]){
location[i] = location[mpos]-distm[i];
stype[i] = 1;
}
else if(dist0[i]>distm[i]){
lef.push_back({distm[i],i});
}
else{
rit.push_back({dist0[i],i});
}
}
}
sort(lef.begin(),lef.end());
sort(rit.begin(),rit.end());
int maxc = 0;
for(pair<int,int> i:lef){
if(getDistance(maxc,i.second)>i.first){
maxc = i.second;
location[i.second] = location[mpos]-i.first;
stype[i.second] = 1;
}
else{
location[i.second] = location[mpos]-i.first;
stype[i.second] = 2;
}
}
int maxd = mpos;
for(pair<int,int> i:rit){
if(getDistance(maxd,i.second)>i.first){
maxd = i.second;
location[i.second] = f+i.first;
stype[i.second] = 2;
}
else{
location[i.second] = f+i.first;
stype[i.second] = 1;
}
}
}
