#include "rail.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5010;
int d0[N];
int d1[N];
void findLocation(int n, int fst, int loc[], int sty[]){
for(int i = 1; i < n; i++)
d0[i] = getDistance(0, i);
int mn = 1;
for(int i = 2; i < n; i++)
if(d0[i] < d0[mn])
mn = i;
//cerr << "mn : " << mn << '\n';
d1[0] = d0[mn];
for(int i = 1; i < n; i++)
d1[i] = getDistance(mn, i);
int L = d0[mn];
loc[0] = fst; sty[0] = 1;
loc[mn] = fst + L; sty[mn] = 2;
vector<int> A, B, C;
for(int i = 1; i < n; i++){
if(i == mn) continue;
if(d0[i] == d1[i] + L){
if(d1[i] < L) B.pb(i);
else A.pb(i);
} else {
C.pb(i);
}
}
for(auto x : B){
sty[x] = 1;
loc[x] = loc[0] + L - d1[x];
}
/*
cerr << "A : ";
for(auto x : A) cerr << x << ' ';
cerr << '\n';
cerr << "B : ";
for(auto x : B) cerr << x << ' ';
cerr << '\n';
cerr << "C : ";
for(auto x : C) cerr << x << ' ';
cerr << '\n';
*/
sort(A.begin(), A.end(), [&](int i, int j){
return d1[i] < d1[j];
});
vector<int> V;
int sz, ds, la;
if(!A.empty()){
la = A[0];
loc[la] = loc[mn] - d1[la];
V.pb(la);
sty[la] = 1;
sz = A.size();
for(int i = 1; i < sz; i++){
ds = getDistance(la, A[i]);
int pos = loc[la] + ds;
bool flg = false;
for(auto x : V){
if(loc[x] <= pos){
if(d1[A[i]] == abs(loc[x] - pos) + d1[x]) flg = true;
break;
}
}
if(flg){
loc[A[i]] = pos;
sty[A[i]] = 2;
} else {
loc[A[i]] = loc[mn] - d1[A[i]];
sty[A[i]] = 1;
la = A[i];
V.pb(la);
}
}
}
sort(C.begin(), C.end(), [&](int i, int j){
return d0[i] < d0[j];
});
if(!C.empty()){
V.clear();
la = C[0];
loc[la] = loc[0] + d0[la];
V.pb(la);
sty[la] = 2;
sz = C.size();
for(int i = 1; i < sz; i++){
ds = getDistance(la, C[i]);
int pos = loc[la] - ds;
bool flg = false;
for(auto x : V){
if(loc[x] >= pos){
if(d0[C[i]] == abs(loc[x] - pos) + d0[x]) flg = true;
break;
}
}
if(flg){
loc[C[i]] = pos;
sty[C[i]] = 1;
} else {
loc[C[i]] = loc[0] + d0[C[i]];
sty[C[i]] = 2;
la = C[i];
V.pb(la);
}
}
}
/*
cerr << "sty : ";
for(int i = 0; i < n; i++) cerr << sty[i] << ' ';
cerr << '\n';
*/
}
/*
1
4
1 1
2 4
2 7
2 9
2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/
