#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int INF = 1e9;
void findLocation(int n, int first, int location[], int stype[])
{
vector<pii> vec;
location[0] = first;
stype[0] = 1;
if (n == 1) return ;
for (int i = 1; i < n; i++) {
int x = getDistance(0, i);
vec.pb({x, i});
}
sort(all(vec));
int x = 0;
int y = vec[0].nd;
location[y] = location[x] + vec[0].st;
stype[y] = 2;
vector<int> znane;
znane.pb(0);
znane.pb(y);
int sz = vec.size();
for (int it = 1; it < sz; it++) {
pii p = vec[it];
int i = p.nd;
int a = getDistance(x, i);
int b = getDistance(y, i);
int px = location[x];
int py = location[y];
int dla = INF;
int dlb = INF;
for (auto v: znane) {
if (stype[v] == 1) {
if (location[v] >= (px + a)) continue;
dlb = min(dlb, py - location[v] + px + a - location[v]);
}
else {
if (location[v] <= (py - b)) continue;
dla = min(dla, location[v] - px + location[v] - (py - b));
}
}
znane.pb(i);
if (dlb == b) {
location[i] = px + a;
stype[i] = 2;
if ((px + a) > py) {
y = i;
}
}
else {
location[i] = py - b;
stype[i] = 1;
if ((py - b) < px) {
x = i;
}
}
// cout << "i = " << i << " location = " << location[i] << " stype = " << stype[i] << " x = " << x << " y = " << y << '\n';
}
}
