#include "rail.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 5010;
int from_0[N];
int from_1[N];
vector<pii> lefty;
vector<pii> wright;
int n;
enum {
C = 1,
D = 2,
};
map<int, int> mp;
void findLocation(int _N, int first, int location[], int stype[])
{
n = _N;
int mn = 1;
Loop (i,1,n) {
from_0[i] = getDistance(0, i);
if (from_0[i] < from_0[mn])
mn = i;
}
int X, Y = 1e9+10;
Loop (i,0,n) {
if (i == mn)
continue;
from_1[i] = getDistance(mn, i);
if (from_1[i] < Y)
Y = from_1[i];
}
X = from_0[mn] - Y;
from_0[0] = 2*(X+Y);
Loop (i,0,n) {
if (i == mn)
continue;
if (from_0[i] - from_1[i] == X-Y)
wright.push_back({from_1[i], i});
else if (from_0[i] - from_1[i] == X+Y)
lefty.push_back({from_1[i], i});
else
assert(false);
}
from_1[mn] = from_0[0];
sort(lefty.begin(), lefty.end());
sort(wright.begin(), wright.end());
assert(lefty.size());
int rD = mn, lC = lefty.front().second;
lefty.erase(lefty.begin());
location[mn] = first + from_0[mn];
stype[mn] = D;
mp[location[mn]] = D;
location[lC] = location[mn] - from_1[lC];
stype[lC] = C;
mp[location[lC]] = C;
for (auto [_, i] : wright) {
int disr = getDistance(rD, i);
int locD = location[0] + from_0[i];
int locC = location[rD] - disr;
int locX = (locC + locD)/2;
if (mp[locX] != D) {
stype[i] = D;
location[i] = locD;
mp[location[i]] = D;
rD = i;
} else {
stype[i] = C;
location[i] = locC;
mp[location[i]] = C;
}
}
for (auto [_, i] : lefty) {
int disl = getDistance(lC, i);
int locC = location[mn] - from_1[i];
int locD = location[lC] + disl;
int locX = (locC + locD)/2;
if (mp[locX] != C) {
stype[i] = C;
location[i] = locC;
mp[location[i]] = C;
lC = i;
} else {
stype[i] = D;
location[i] = locD;
mp[location[i]] = D;
}
}
}
