#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(max(loc[r]-dr, loc[l]));
if (it!=d.end()&&dl==abs(loc[r]-loc[l])+dr-2*abs(loc[r]-*it)){
type[ord[i].se]=1;
loc[ord[i].se]=loc[r]-dr;
goto end;
}
it=c.lower_bound(min(loc[l]+dl, loc[r]));
if (it!=c.begin()){
--it;
if (dr==abs(loc[r]-loc[l])+dl-2*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;
}
}
