#include "rail.h"
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
const int maxn=5e3+5;
pair < int, int > dist[maxn];
vector < int > desne;
vector < int > lijeve;
vector < int > pot;
void findLocation(int n, int pos, int sol1[], int sol2[]){
for(int i=1; i<n; i++){
dist[i-1]={getDistance(0, i), i};
}
sol1[0]=pos;
sol2[0]=1;
sort(dist, dist+n-1);
int l=0;
lijeve.push_back(l);
int d=dist[0].second;
int x;
sol1[d]=pos+dist[0].first;
sol2[d]=2;
desne.push_back(d);
int q1, q2;
bool p;
for(int i=1; i<n-1; i++){
x=dist[i].second;
// cout << "na " << x << endl;
q1=getDistance(l, x);
q2=getDistance(d, x);
for(int j=0; j<(int)desne.size(); j++){
if(sol1[desne[j]]-sol1[l]<q1 && (!j || sol1[desne[j]]*2-q1-sol1[l]>sol1[desne[j-1]])){
pot.push_back(sol1[desne[j]]*2-q1-sol1[l]);
}
}
p=0;
for(int j=0; j<(int)pot.size(); j++){
if(sol1[d]-pot[j]==q2){
assert(!p);
assert(pot[j]>=0);
p=1;
sol1[x]=pot[j];
sol2[x]=1;
lijeve.push_back(x);
int poz=lijeve.size()-1;
while(poz>0 && sol1[lijeve[poz]]<sol1[lijeve[poz-1]]){
swap(lijeve[poz], lijeve[poz-1]);
poz--;
}
l=lijeve[0];
}
}
pot.clear();
if(p){
continue;
}
for(int j=0; j<(int)lijeve.size(); j++){
if(sol1[d]-sol1[lijeve[j]]<q2 && (j==(int)lijeve.size()-1 || sol1[lijeve[j]]*2+q2-sol1[d]<sol1[lijeve[j+1]])){
pot.push_back(sol1[lijeve[j]]*2+q2-sol1[d]);
}
}
for(int j=0; j<(int)pot.size(); j++){
if(pot[j]-sol1[l]==q1){
assert(!p);
p=1;
sol1[x]=pot[j];
sol2[x]=2;
desne.push_back(x);
int poz=desne.size()-1;
while(poz>0 && sol1[desne[poz]]<sol1[desne[poz-1]]){
swap(desne[poz], desne[poz-1]);
poz--;
}
d=desne.back();
}
}
pot.clear();
if(p){
continue;
}
if(q1-dist[i].first==sol1[0]-sol1[l]){
sol1[x]=sol1[l]+q1;
sol2[x]=2;
desne.push_back(x);
int poz=desne.size()-1;
while(poz>0 && sol1[desne[poz]]<sol1[desne[poz-1]]){
swap(desne[poz], desne[poz-1]);
poz--;
}
d=desne.back();
}
else{
sol1[x]=sol1[d]-q2;
sol2[x]=1;
lijeve.push_back(x);
int poz=lijeve.size()-1;
while(poz>0 && sol1[lijeve[poz]]<sol1[lijeve[poz-1]]){
swap(lijeve[poz], lijeve[poz-1]);
poz--;
}
l=lijeve[0];
}
// cout << l << ' ' << d << endl;
}
/* cout << "kraj--------" << endl;
for(int i=0; i<n; i++){
cout << sol2[i] << ' ' << sol1[i] << endl;
}*/
}
