#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int n, int first, int location[], int stype[]){
stype[0] = 1;
location[0] = first;
vector<pair<int, int>> dist0;
vector<int> di0(n), di1(n);
for(int i = 1; i < n; i++){
int d = getDistance(0, i);
di0[i] = d;
dist0.emplace_back(d, i);
}
sort(dist0.begin(), dist0.end());
int s = dist0[0].second;
stype[s] = 2;
location[s] = first+dist0[0].first;
for(int i = 1; i < n; i++){
if(i != s) di1[i] = getDistance(s, i);
}
map<int, int> C, D;
C.emplace(first, 0);
D.emplace(location[dist0[0].second], dist0[0].second);
for(int i = 1; i < n-1; i++){
auto [d0, ind] = dist0[i];
if(di0[ind] == di0[s] + di1[ind]){
if(di1[ind] < di0[s]){
stype[ind] = 1;
location[ind] = location[s]-di1[ind];
C.emplace(location[ind], ind);
}
else{
int dc = getDistance(C.begin()->second, ind);
int lc = C.begin()->first;
int p = (location[s]-di1[ind] + lc+dc) / 2;
if(C.count(p)){
stype[ind] = 2;
location[ind] = lc+dc;
D.emplace(location[ind], ind);
}
else{
stype[ind] = 1;
location[ind] = location[s]-di1[ind];
C.emplace(location[ind], ind);
}
}
}
else{
int dd = getDistance(D.rbegin()->second, ind);
int rd = D.rbegin()->first;
int p = (rd-dd + first+d0) / 2;
if(D.count(p)){
stype[ind] = 1;
location[ind] = rd-dd;
C.emplace(location[ind], ind);
}
else{
stype[ind] = 2;
location[ind] = first+d0;
D.emplace(location[ind], ind);
}
}
}
}
