#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
void findLocation(int N, int first, int location[], int stype[]) {
location[0] = first;
stype[0] = 1;
vector<int> dist0(N);
for (int i = 1; i < N; ++i) {
dist0[i] = getDistance(0, i);
}
int p = 1;
for (int i = 2; i < N; ++i) {
if (dist0[p] > dist0[i]) {
p = i;
}
}
location[p] = first + dist0[p];
stype[p] = 2;
vector<int> distp(N);
vector<int> left;
vector<int> right;
for (int i = 1; i < N; ++i) {
if (i != p) {
distp[i] = getDistance(p, i);
if (dist0[i] == distp[i] + dist0[p] && distp[i] <= dist0[p]) {
location[i] = location[p] - distp[i];
stype[i] = 1;
} else {
if (dist0[i] == distp[i] + dist0[p]) {
left.push_back(i);
} else {
right.push_back(i);
}
}
}
}
{
sort(left.begin(), left.end(), [&](int a, int b) {
return distp[a] < distp[b];
});
vector<int> down;
down.push_back(0);
for (auto i : left) {
int foo = location[p] - distp[i];
int bar = location[down.back()] + getDistance(down.back(), i);
int near = -1;
for (auto j : down) {
if (location[j] <= bar) {
near = j;
break;
}
}
if (location[near] - foo == bar - location[near]) {
location[i] = bar;
stype[i] = 2;
} else {
location[i] = foo;
stype[i] = 1;
down.push_back(i);
}
}
}
{
sort(right.begin(), right.end(), [&](int a, int b) {
return dist0[a] < dist0[b];
});
vector<int> up;
up.push_back(p);
for (auto i : right) {
int foo = location[0] + dist0[i];
int bar = location[up.back()] - getDistance(up.back(), i);
int near = -1;
for (auto j : up) {
if (location[j] >= bar) {
near = j;
break;
}
}
if (foo - location[near] == location[near] - bar) {
location[i] = bar;
stype[i] = 1;
} else {
location[i] = foo;
stype[i] = 2;
up.push_back(i);
}
}
}
}
