#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
void findLocation(int n, int f, int loc[], int tpe[]) {
loc[0]=f;
tpe[0]=1;
vector<pi> ord;
for (int i=1; i<n; i++) {
ord.pb({getDistance(0,i),i});
}
sort(all(ord));
loc[ord[0].se]=f+ord[0].fi;
tpe[ord[0].se]=2;
int l=0,r=ord[0].se;
set<int> inds1={loc[0]};
set<int> inds2={loc[r]};
for (int i=1; i<n-1; i++) {
int cur=ord[i].se,dst=ord[i].fi;
loc[cur]=-1;
int dstl=getDistance(l,cur),dstr=getDistance(r,cur);
{// ( ) )
int tloc=loc[l]+dstl;
int pos=*prev(inds1.lower_bound(min(tloc,loc[r])));
if (dstr==tloc+loc[r]-2*pos) {
loc[cur]=tloc;
tpe[cur]=2;
}
}
{// ( ( )
int tloc=loc[r]-dstr;
int pos=*inds2.lower_bound(max(tloc,loc[l]));
if (dstl==2*pos-tloc-loc[l]) {
loc[cur]=tloc;
tpe[cur]=1;
}
}
if (loc[cur]==-1) {
int tloc=loc[r]-dstr;
int pos=*inds2.lower_bound(loc[0]);
if (dst==2*pos-tloc-loc[0]) {
loc[cur]=tloc;
tpe[cur]=1;
}
else {
loc[cur]=loc[l]+dstl;
tpe[cur]=2;
}
}
if (tpe[cur]==1) {
inds1.insert(loc[cur]);
if (loc[cur]<loc[l]) {
l=cur;
}
}
else {
inds2.insert(loc[cur]);
if (loc[cur]>loc[r]) {
r=cur;
}
}
}
}
