#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef complex<double> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 5e3 + 10;
int n, h[maxn][2], idx[maxn];
bool cmp(int x, int y){
return h[x][0] < h[y][0];
}
void findLocation(int N, int first, int loc[], int type[]){
n = N;
for (int i = 1; i < n; i++){
h[i][0] = getDistance(0, i);
idx[i] = i;
}
sort(idx, idx + n, cmp);
h[0][1] = h[idx[1]][0];
for (int i = 1; i < n; i++){
if (i == idx[1]) continue;
h[i][1] = getDistance(idx[1], i);
}
loc[0] = first;
loc[idx[1]] = first + h[idx[1]][0];
type[0] = 1;
type[idx[1]] = 2;
int l = 0, r = idx[1];
for (int i = 2; i < n; i++){
if (h[idx[1]][0] + h[idx[i]][1] == h[idx[i]][0]){
if (h[idx[i]][1] <= h[idx[1]][0]){
type[idx[i]] = 1;
loc[idx[i]] = loc[idx[1]] - h[idx[i]][1];
continue;
}
int dis = getDistance(l, idx[i]);
int tmp = (dis + h[idx[i]][1] - h[l][1]) / 2;
tmp = dis - tmp;
tmp += loc[l];
bool flg = true;
for (int j = 0; j < i; j++){
if (loc[idx[j]] == tmp && type[idx[j]] == 1) flg = false;
}
if (flg){
loc[idx[i]] = loc[idx[1]] - h[idx[i]][1];
type[idx[i]] = 1;
l = idx[i];
}
else{
loc[idx[i]] = loc[l] + dis;
type[idx[i]] = 2;
}
continue;
}
int dis = getDistance(r, idx[i]);
int tmp = (dis + h[idx[i]][0] - h[r][0]) / 2;
tmp = dis - tmp;
tmp = loc[r] - tmp;
bool flg = true;
for (int j = 0; j < i; j++){
if (loc[idx[j]] == tmp && type[idx[j]] == 2) flg = false;
}
if (flg){
loc[idx[i]] = loc[idx[0]] + h[idx[i]][0];
type[idx[i]] = 2;
r = idx[i];
}
else{
loc[idx[i]] = loc[r] - dis;
type[idx[i]] = 1;
}
}
}
