#include <bits/stdc++.h>
#include "rail.h"
#define gd getDistance
#define eb emplace_back
using namespace std;
void findLocation(int N, int first, int L[], int T[]) {
vector<int> D(N), S;
for (int i=1; i<N; i++) S.eb(i), D[i]=gd(0, i);
sort(S.begin(), S.end(), [&](int x, int y) { return D[x]<D[y]; });
int l=0, r=S[0];
L[l]=0, L[r]=D[r];
T[l]=1, T[r]=2;
map<int, int> M;
M[0]=1, M[D[r]]=2;
for (int i=1; i<N-1; i++) {
int n=S[i];
int d1=gd(l, n), d2=gd(r, n), x=(L[l]+L[r]+d1-d2)/2;
if (M[x]==1||(M[x]==0&&x>0)) {
int dn=L[l]+d1;
L[n]=dn;
T[n]=2;
M[dn]=2;
if (dn>L[r]) r=n;
}
else {
int dn=L[r]-d2;
L[n]=dn;
T[n]=1;
M[dn]=1;
if (dn<L[l]) l=n;
}
}
for (int i=0; i<N; i++) L[i]=L[i]+first;
}
