#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr << #x << ": " << x << endl;
#define sep ' '
const ll MAXN = 1e6 + 10;
int n, f, d1[MAXN], d2[MAXN], d3[MAXN];
inline int get(int i, int j) {
return getDistance(i, j);
}
void findLocation(int N, int first, int location[], int stype[]) {
n = N;
f = first;
location[0] = f;
stype[0] = 1;
if (n == 1) return;
f = first;
int mn = 1;
for (int i = 1; i < n; i++) {
d1[i] = get(0, i);
if (d1[i] < d1[mn])
mn = i;
}
location[mn] = location[0] + d1[mn];
stype[mn] = 2;
for (int i = 0; i < n; i++) {
if (i != mn) {
d2[i] = get(mn, i);
}
}
for (int i = 0; i < n; i++) {
if (i == 0 || i == mn) continue;
if (d1[i] == d1[mn] + d2[i]) {
stype[i] = 1;
location[i] = location[mn] - d2[i];
} else {
stype[i] = 2;
location[i] = location[0] + d1[i];
}
}
}
// mn location
