#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
static vector <int> loc, type;
int get(int x, int y, int tx, int ty, int n) {
if(x > y) {
swap(x, y);
swap(tx, ty);
}
if(tx == 1 && ty == 2) {
return y - x;
}
if(tx == 1 && ty == 1) {
int mn = 1e9;
for(int i = 0; i < n; i++) {
if(type[i] == 2 && loc[i] >= y) {
mn = min(mn, loc[i]);
}
}
return mn - x + get(y, mn, ty, 2, n);
}
int mx = -1;
for(int i = 0; i < n; i++) {
if(type[i] == 1 && loc[i] <= x) {
mx = max(mx, loc[i]);
}
}
return x - mx + get(mx, y, 1, ty, n);
}
static map <pair <int, int>, int> qry;
inline int query(int a, int b) {
if(a > b) swap(a, b);
if(qry[{a, b}]) {
return qry[{a, b}];
}
return qry[{a, b}] = getDistance(a, b);
}
void findLocation(int n, int first, int location[], int stype[]) {
vector < pair <int, int> > arr;
int i, l = 0;
for(i = 1; i < n; i++) {
arr.push_back({query(0, i), i});
}
sort(arr.begin(), arr.end());
int r = arr[0].second;
loc.resize(n), type.resize(n);
loc[r] = arr[0].first + first; type[r] = 2;
loc[0] = first; type[0] = 1;
for(i = 1; i < arr.size(); i++) {
int k = arr[i].second;
int cur = loc[l] + query(l, k);
//cerr << get(cur, loc[r], 2, 2, n) << " " << query(k, r) << " " << get(cur, loc[0], 2, 1, n) << " " << query(0, k) << "\n" ;
if(get(cur, loc[r], 2, 2, n) == query(k, r) && get(cur, loc[0], 2, 1, n) == query(0, k)) {
loc[k] = cur;
type[k] = 2;
if(loc[k] > loc[r]) {
r = k;
}
}
else {
loc[k] = loc[r] - query(r, k);
type[k] = 1;
if(loc[l] > loc[k]) {
l = k;
}
}
}
for(i = 0; i < n; i++) {
location[i] = loc[i];
stype[i] = type[i];
//cerr << location[i] << " " << stype[i] << "\n";
}
}
