#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define oo 1000000000
void findLocation(int n, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
vector<int> d0(n);
for (int i = 1; i < n; ++i) d0[i] = getDistance(0, i);
vector<bool> visited(n); visited[0] = true;
if (n == 1) return;
int mni = -1;
for (int i = 0; i < n; ++i){
if (!visited[i] && (mni == -1 || d0[i] < d0[mni])) mni = i;
}
location[mni] = location[0] + d0[mni];
stype[mni] = 2;
visited[mni] = true;
int l = 0, r = mni;
vector<pair<int, int>> c, d;
c.push_back({-location[l], l});
d.push_back({location[r], r});
for (int j = 2; j < n; ++j) {
int cur = -1;
for (int i = 0; i < n; ++i){
if (!visited[i] && (cur == -1 || d0[i] < d0[cur])) cur = i;
}
visited[cur] = true;
int dl = getDistance(l, cur), dr = getDistance(r, cur);
auto it = upper_bound(d.begin(), d.end(), make_pair(location[r] - dr, cur));
if (location[r] - dr > location[l] && it != d.end() && 2 * location[it->second] - dl - location[l] == location[r] - dr) {
stype[cur] = 1;
location[cur] = location[r] - dr;
continue;
}
it = upper_bound(c.begin(), c.end(), make_pair(-(location[l] + dl), cur));
if (location[l] + dl < location[r] && it != c.end() && dr - location[r] + 2 * location[it->second] == location[l] + dl) {
stype[cur] = 2;
location[cur] = location[l] + dl;
continue;
}
if (d0[cur] == d0[mni] + dr - (location[r] - location[mni])) {
stype[cur] = 1;
location[cur] = location[r] - dr;
c.push_back(make_pair(-location[cur], cur));
l = cur;
} else {
stype[cur] = 2;
location[cur] = location[l] + dl;
d.push_back(make_pair(location[cur], cur));
r = cur;
}
}
}
