#include <bits/stdc++.h>
#include "rail.h"
#define eb emplace_back
using namespace std;
const int MX = 5e3 + 5;
const int INF = 1e9;
int L[MX], *T, D[2][MX];
int X, re;
int gd(int s, int e) {
if (s==e) return 0;
return getDistance(s, e);
}
void findLocation(int N, int first, int location[], int stype[]) {
T=stype;
T[0]=1;
int mn=INF;
for (int i=1; i<N; i++) {
D[0][i]=gd(0, i);
if (mn>D[0][i]) mn=D[0][i], X=i;
}
T[X]=2, L[X]=mn;
mn=INF;
for (int i=1; i<N; i++) if (i!=X) {
D[1][i]=gd(X, i);
if (mn>D[1][i]) mn=D[1][i], re=i;
}
vector<int> l, m, r;
for (int i=1; i<N; i++) if (i!=X) {
if (D[1][i]<L[X]) m.eb(i);
else if (D[0][i]==D[1][i]+L[X]) l.eb(i);
else if (D[0][i]-L[X]==D[1][i]-2*mn) r.eb(i);
else assert(false);
}
for (int i=0; i<N; i++) location[i]=L[i]+N;
}
