#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5e3+5;
int l, r, vl[nx];
vector<pair<int, int>> d;
set<int> C, D;
void findLocation(int N, int first, int location[], int stype[])
{
location[0]=first;
stype[0]=1;
for (int i=1; i<N; i++) vl[i]=getDistance(0, i);
for (int i=1; i<N; i++) d.push_back({vl[i], i});
sort(d.begin(), d.end());
//cout<<"p "<<d[0].second<<'\n';
location[d[0].second]=first+d[0].first;
stype[d[0].second]=2;
l=0, r=d[0].second;
C.insert(first);
D.insert(first+d[0].first);
for (int i=1; i<N-1; i++)
{
int u=d[i].second, dl=getDistance(l, u), dr=getDistance(r, u), pos=location[l]+dl;
if (location[r]-*(prev(C.upper_bound(pos)))+pos-*(prev(C.upper_bound(pos)))==dr) location[u]=pos, D.insert(pos), stype[u]=2;
else
{
pos=location[r]-dr;
if (*D.lower_bound(pos)-location[l]+*D.lower_bound(pos)-pos==dl) location[u]=pos, C.insert(pos), stype[u]=1;
else if (d[i].first==2*location[d[0].second]-first-pos) location[u]=pos, C.insert(pos), stype[u]=1;
else location[u]=location[l]+dl, D.insert(location[u]), stype[u]=2;
}
if (location[u]<location[l]) l=u;
if (location[u]>location[r]) r=u;
}
}
