#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 5003;
int d_[MXN][MXN];
inline int d(int i, int j) {
if(i>j) swap(i, j);
if(d_[i][j]) return d_[i][j];
return d_[i][j] = getDistance(i, j);
}
void findLocation(int n, int fir, int x[], int s[]) {
x[0] = fir;
fill(s, s+n, 0);
s[0] = 1;
if(n==1) return;
int L=0, R = -1;
int mn = 1e9;
for(int i=1; i<n; i++)
if(d(0, i) < mn) {
mn = d(0, i);
R = i;
}
s[R] = 2;
x[R] = x[0] + d(0, R);
for(int t=0, i, k; t<n-2; t++) {
i = -1;
for(int j=0; j<n; j++)
if(!s[j] && (i==-1 || d(0, i)>d(0,j)))
i=j;
x[i] = x[L] + d(L, i);
k = L;
for(int j=0; j<n; j++)
if(s[j]==1 && x[j]>x[k] && x[j]<x[i])
k=j;
if(x[i] < x[0] && d(R, i) == x[i] + x[R] - 2*x[k]) {
s[i] = 2;
continue;
}
x[i] = x[R] - d(R, i);
k = R;
for(int j=0; j<n; j++)
if(s[j]==2 && x[j]<x[k] && x[j]>x[i])
k=j;
if(x[i] > x[0] && d(L, i) == 2*x[k] - x[i] - x[L]) {
s[i] = 1;
continue;
}
k = -1;
for(int j=0; j<n; j++)
if(s[j]==2 && x[L]<x[j] && x[j]<x[0])
k = j;
if(k!=-1) {
if(d(i, L) - d(i, 0) == x[0]-x[L]) {
s[i] = 2;
x[i] = x[L] + d(L, i);
R = i;
}
else {
s[i] = 1;
x[i] = x[R] - d(R, i);
L = i;
}
continue;
}
x[i] = x[R] - d(i, R);
k = R;
for(int j=0; j<n; j++)
if(s[j]==2 && x[j]<x[k] && x[j]>x[0])
k=j;
if(x[i] < x[L] && d(i, 0) == 2*x[k] - x[0] - x[i]) {
s[i] = 1;
L = i;
continue;
}
s[i] = 2;
x[i] = x[L] + d(L, i);
R = i;
}
}
/*
L k i 0 R
( ( ) ( )
if( x[L] + d(L, i) < x[0])
if( d(R, i) == x[L] + d(L, i) + x[R] - 2*x[k])
ok
L 0 i k R
( ( ( ) )
if( x[R] - d(R, i) > x[0])
if( d(L, i) == 2*x[k] - x[L] - (x[R] - d(R, i)))
ok
if {
L ? 0 r
( ) ( )
if( d(i, L) - d(i, 0) == x[0]-x[L] ) 4
else 1
}
else {
i L 0 k R
( ( ( ) )
if( x[R] - d(i, R) < x[L])
if( d(i, 0) == 2*x[k] - x[0] - (x[R] - d(i, R)))
ok
}
*/
