#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int dis[2][N];
void findLocation(int n, int first, int location[], int stype[]) {
location[0] = first, stype[0] = 1;
for (int i = 1; i < n; ++i) {
dis[0][i] = getDistance(0, i);
}
int p1 = 1;
for (int i = 2; i < n; ++i) {
if (dis[0][p1] > dis[0][i]) p1 = i;
}
location[p1] = location[0] + dis[0][p1], stype[p1] = 2;
vector<int> vecl, vecr;
for (int i = 1; i < n; ++i) {
if (i == p1) continue;
dis[1][i] = getDistance(p1, i);
if (dis[1][i] <= dis[0][p1]) {
location[i] = location[p1] - dis[1][i], stype[i] = 1;
// cout << "ax " << i << '\n';
}
else {
if (dis[1][i] == dis[0][i] + dis[0][p1]) vecr.push_back(i);
else vecl.push_back(i);
}
}
sort(vecl.begin(), vecl.end(), [&] (int x, int y) {
return dis[1][x] < dis[1][y];
});
sort(vecr.begin(), vecr.end(), [&] (int x, int y) {
return dis[0][x] < dis[0][y];
});
// for (auto i : vecl) cout << i << ' '; cout << '\n';
// for (auto i : vecr) cout << i << ' '; cout << '\n';
int cur;
vector<int> vec;
{
cur = p1;
vec.clear();
vec.push_back(p1);
for (auto i : vecr) {
int tmp1 = getDistance(cur, i);
int tmp2 = dis[0][i] + location[0];
int tmp3 = location[cur] - tmp1;
int p = -1;
for (auto j : vec) {
if (location[j] >= tmp3) p = j;
}
if (tmp2 - location[p] == location[p] - tmp3) {
location[i] = tmp3, stype[i] = 1;
}
else {
location[i] = tmp2, stype[i] = 2, cur = i, vec.push_back(i);
}
}
}
{
cur = 0;
vec.clear();
vec.push_back(0);
for (auto i : vecl) {
int tmp1 = getDistance(cur, i);
int tmp2 = location[p1] - dis[1][i];
int tmp3 = location[cur] + tmp1;
int p = -1;
for (auto j : vec) {
if (location[j] <= tmp3) p = j;
}
if (tmp2 - location[p] == location[p] - tmp3) {
location[i] = tmp3, stype[i] = 2;
}
else {
location[i] = tmp2, stype[i] = 1, cur = i, vec.push_back(i);
}
}
}
}
