#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
void findLocation(int n, int start, int loc[], int type[]){
type[0]=1;
loc[0]=start;
vector<pii> ord;
for (int i=1; i<n; ++i)ord.pb(mp(getDistance(0, i), i));
sort(ord.begin(), ord.end());
type[ord[0].se]=2;
loc[ord[0].se]=start+ord[0].fi;
int l=0, r=ord[0].se;
set<int> c, d;
c.insert(start);
d.insert(start+ord[0].fi);
for (int i=1; i<ord.size(); ++i){
int dl=getDistance(l, ord[i].se), dr=getDistance(r, ord[i].se);
auto it=d.upper_bound(loc[r]-dr);
if (it!=d.end()&&(long long)dl==((long long)abs(loc[r]-loc[l])+(long long)dr-2ll*abs(loc[r]-*it))){
type[ord[i].se]=1;
loc[ord[i].se]=loc[r]-dr;
goto end;
}
it=c.lower_bound(loc[l]+dl);
if (it!=c.begin()){
--it;
if ((long long)dr==((long long)abs(loc[r]-loc[l])+(long long)dl-2ll*abs(loc[l]-*it))){
type[ord[i].se]=2;
loc[ord[i].se]=loc[l]+dl;
goto end;
}
}
if (dl<dr){
type[ord[i].se]=2;
loc[ord[i].se]=dl+loc[l];
}
else{
type[ord[i].se]=1;
loc[ord[i].se]=loc[r]-dr;
}
end:;
if (type[ord[i].se]==1)c.insert(loc[ord[i].se]);
if (type[ord[i].se]==2)d.insert(loc[ord[i].se]);
if (type[ord[i].se]==1&&loc[ord[i].se]<loc[l])l=ord[i].se;
if (type[ord[i].se]==2&&loc[ord[i].se]>loc[r])r=ord[i].se;
}
}
