#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using idata = vector<int>;
using bdata = vector<bool>;
template<typename T>
using lpq = priority_queue<T, vector<T>, greater<T>>;
using ii = pair<int, int>;
idata distance0;
const int DTYPE = 2;
const int CTYPE = 1;
void findLocation(int N, int first, int location[], int stype[])
{
location[0] = first;
stype [0] = 1;
distance0.resize(N, -1);
int minD = 1e9;
int minP = -1;
for (int i = 1; i < N; i ++) {
distance0[i] = getDistance(0, i);
if (distance0[i] >= minD) continue ;
minD = distance0[i];
minP = i;
}
int lefD = minP;
int rigD = minP;
location[minP] = first + minD;
stype [minP] = DTYPE;
int lefC = -1;
lpq<ii> queue;
for (int i = 1; i < N; i ++)
if (i != minP)
queue.push({ distance0[i], i });
set<int> rigDPos = { first + minD };
set<int> lefCPos = { };
while (queue.size() != 0) {
const auto nextDP = queue.top(); queue.pop();
int next = nextDP.second;
int nextDist = getDistance(lefD, next);
int offDist = nextDist + minD;
int resDist = distance0[next];
if (resDist == offDist) {
bool isLefC = true;
int passDist;
if (lefC != -1) {
passDist = getDistance(lefC, next);
int potPos = location[lefC] + passDist;
auto it = lefCPos.lower_bound( potPos ); it --;
int potLefC = *it;
int potDist = first + 2 * minD + potPos - 2 * potLefC;
isLefC = potDist != resDist;
}
if (isLefC) {
lefC = next;
location[next] = first + minD - nextDist;
stype [next] = CTYPE;
lefCPos.insert( location[next] );
} else {
location[next] = passDist + location[lefC];
stype [next] = DTYPE;
}
} else {
bool isRigD;
int passDist = getDistance(rigD, next);
int potLocat = location[rigD] - passDist;
int potRigD = *rigDPos.upper_bound(potLocat);
int potDist = 2 * potRigD - potLocat - first;
isRigD = potDist != resDist;
if (isRigD) {
rigD = next;
location[next] = first + distance0[next];
stype [next] = DTYPE;
rigDPos.insert(location[next]);
} else {
location[next] = location[rigD] - passDist;
stype [next] = CTYPE;
}
}
}
}
