#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 = 0;
for (int i = 0; i < n; i++) {
if (i != 0) {
d1[i] = get(0, i);
d2[i] = get(i, 0);
stype[i] = (d1[i] == d2[i] ? 2 : 1);
if (stype[i] == 1) {
if (d1[i] < d2[i]) location[i] = location[0] + d1[i];
else location[i] = location[0] - d1[i];
if (location[i] < location[mn]) mn = i;
}
}
}
for (int i = 0; i < n; i++) {
if (i != mn) {
d3[i] = get(mn, i);
if (stype[i] == 2)
location[i] = location[mn] + d3[i];
}
}
}
