#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, val[maxn], idx[maxn];
vector<int> v;
bool cmp(int x, int y){
return val[x] < val[y];
}
void findLocation(int N, int first, int loc[], int type[]){
n = N;
for (int i = 1; i < n; i++){
idx[i] = i;
val[i] = getDistance(0, i);
}
sort(idx + 1, idx + n, cmp);
loc[0] = first;
loc[idx[1]] = first + val[idx[1]];
type[0] = 1;
type[idx[1]] = 2;
v.push_back(0);
v.push_back(idx[1]);
for (int i = 2; i < n; i++){
int l = v[0], r = v.back();
int x = getDistance(l, idx[i]);
int y = getDistance(r, idx[i]);
int z = loc[r] - loc[l];
int tmp = x + y - z;
tmp >>= 1;
int rng = loc[l] + x - tmp;
for (auto u: v){
if (loc[u] == rng){
if (type[u] == 1){
loc[idx[i]] = rng + tmp;
type[idx[i]] = 2;
}
else{
loc[idx[i]] = rng - tmp;
type[idx[i]] = 1;
}
}
}
vector<int> v2;
bool flg = false;
for (auto u: v){
if (loc[u] >= loc[idx[i]] && !flg){
v2.push_back(idx[i]);
flg = true;
}
v2.push_back(u);
}
if (flg == false) v2.push_back(idx[i]);
v = v2;
}
}
