#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[5050], b[5050];
inline int myabs(int x){
if (x<0) return -x;
return x;
}
void solve(vector<pair<int, int>> &X, int typ, int pos, int n, int location[], int stype[]){
int mul = typ?1:-1;
sort(X.begin(), X.end());
location[X[0].second] = pos + X[0].first * mul;
stype[X[0].second] = typ;
int Li = X[0].second, Lx = pos + X[0].first * mul;
for (int i=1;i<(int)X.size();i++){
int x = pos + X[i].first * mul;
if (getDistance(Li, X[i].second)==myabs(Lx-x)){
location[X[i].second] = Lx - myabs(Lx-x)*mul;
stype[X[i].second] = typ^1;
}
else{
location[X[i].second] = x;
stype[X[i].second] = typ;
Li = X[i].second, Lx = x;
}
}
}
void findLocation(int n, int first, int location[], int stype[]){
//location[0] = first;
//stype[0] = 1;
int mn = 1e9, fd = -1;
for (int i=1;i<n;i++){
a[i] = getDistance(0, i);
if (a[i] < mn){
mn = a[i], fd = i;
}
}
//location[fd] = first + mn;
//stype[fd] = 2;
b[0] = a[1];
vector<pair<int, int>> L = {{mn, 0}}, R = {{0, 1}};
for (int i=2;i<n;i++){
b[i] = getDistance(1, i);
if (a[i]==b[i]+mn) L.emplace_back(b[i], i);
else R.emplace_back(a[i]-mn, i);
}
solve(L, 0, first+mn, n, location, stype);
solve(R, 1, first+mn, n, location, stype);
for (int i=0;i<n;i++) stype[i]++;
//printf("\n");
//for (int i=0;i<n;i++) printf("%d %d\n", stype[i], location[i]);
}
