#include "rail.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
// getDistance(int a, int b)
void findLocation(int n, int first, int location[], int stype[]) {
// find closest;
// cout << getDistance(0, 2) << '\n';
// cout << getDistance(0, 3) << '\n';
// return;
int d[2][n];
int closest = 1, A = 0, B, C;
for (int i = 1; i < n; i++) {
d[0][i] = getDistance(A, i);
if (d[0][i] < d[0][closest]) closest = i;
}
B = closest;
int second = first + d[0][B];
stype[A] = 1, location[A] = first;
stype[B] = 2, location[B] = second;
d[1][A] = d[0][B];
for (int i = 1; i < n; i++) {
if (i == B) continue;
d[1][i] = getDistance(B, i);
}
vector <PII> left, right;
int dist = d[0][B];
for (int i = 1; i < n; i++) {
if (i == B) continue;
if (min(d[0][i], d[1][i]) < dist) {
if (d[0][i] < d[1][i])
stype[i] = 2, location[i] = first + d[0][i];
else
stype[i] = 1, location[i] = second - d[1][i];
continue;
}
if (d[0][i] < d[1][i]) right.pb({d[0][i], i});
else left.pb({d[1][i], i});
}
sort(ALL(left));
sort(ALL(right));
// cout << "right: ";
// for (int i = 1; i< n; i++) cout << i << " " << d[0][i] << '\n';
if (!right.empty()) {
// for (auto el : right) cout << el.ss << "," << el.ff << ' ';
int par = right[0].ss;
vector <int> pars(1, par);
stype[par] = 2, location[par] = first + d[0][par];
for (int i = 1; i < right.size(); i++) {
int dist, j; tie(dist, j) = right[i];
bool same = 1;
for (auto el : pars) {
int cur = getDistance(el, j);
if (d[0][j] == d[0][el] + cur && same)
stype[j] = 1, location[j] = location[el] - cur, same = 0;
}
if (same)
stype[j] = 2, location[j] = first + d[0][j], pars.pb(j);
}
}
// cout << '\n';
// cout << "left: ";
if (!left.empty()) {
// for (auto el : left) cout << el.ss << "," << el.ff << ' ';
int par = left[0].ss;
vector <int> pars(1, par);
stype[par] = 1, location[par] = second - d[1][par];
for (int i = 1; i < left.size(); i++) {
int dist, j; tie(dist, j) = left[i];
bool same = 1;
for (auto el : pars) {
int cur = getDistance(el, j);
if (d[0][j] == d[0][el] + cur && same)
stype[j] = 2, location[j] = location[el] + cur, same = 0;
}
if (same)
stype[j] = 1, location[j] = second - d[1][j], pars.pb(j);
}
}
// cout << '\n';
}
