#include "rail.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
const int MAXN = 5000 + 17;
pii odl[MAXN];
vector<int> vc;
vector<int> vd;
void findLocation(int N, int first, int location[], int stype[]) {
for (int i = 1; i < N; i ++) {
odl[i].nd = i;
odl[i].st = getDistance(0, i);
}
odl[0] = {0, 0};
sort(odl, odl + N);
stype[0] = 1;
location[0] = first;
vc.pb(first);
if (N == 1) {
return;
}
stype[odl[1].nd] = 2;
location[odl[1].nd] = first + odl[1].st;
vd.pb(location[odl[1].nd]);
int L = 0, R = odl[1].nd;
for (int i = 2; i < N; i ++) {
int a = odl[i].nd;
int b = getDistance(L, a);
int c = getDistance(R, a);
location[a] = -1;
//do L
int kand = location[L] + b;
int pos = -1;
for (auto x : vc) {
if (x <= min(kand, location[R])) {
pos = max(pos, x);
}
}
if (pos != -1 && c == (kand + location[R] - 2 * pos)) {
location[a] = kand;
stype[a] = 2;
}
//do R
if (location[a] == -1) {
location[a] = location[R] - c;
stype[a] = 1;
}
if (stype[a] == 1) {
if (location[a] < location[L]) {
L = a;
}
vc.pb(a);
}
if (stype[a] == 2) {
if (location[a] > location[R]) {
R = a;
}
}
}
}
