#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 });
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 offpDist = passDist + distance0[lefC];
isLefC = resDist != offpDist;
}
if (isLefC) {
lefC = next;
location[next] = first + minD - nextDist;
stype [next] = CTYPE;
} else {
location[next] = passDist + location[lefC];
stype [next] = DTYPE;
}
} else {
bool isRigD;
int passDist = getDistance(rigD, next);
int offpDist = passDist + distance0[rigD];
isRigD = resDist != offpDist;
if (isRigD) {
rigD = next;
location[next] = first + distance0[next];
stype [next] = DTYPE;
} else {
location[next] = location[rigD] - passDist;
stype [next] = CTYPE;
}
}
}
}
