#include "rail.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 5005;
int dist[2][N], first;
vector <int> lft, op, cl;
bool cmp1 (int a, int b) {
return dist[0][a] < dist[0][b];
}
void findLocation(int n, int pos, int a[], int t[])
{
int mn = 1e9 + 7, ind;
a[0] = pos, t[0] = 1;
for (int i = 1; i < n; i++) {
dist[0][i] = getDistance(0, i);
if (dist[0][i] < mn) {
mn = dist[0][i];
ind = i;
}
// cout << i << " -> " << dist[0][i] << endl;
}
a[ind] = pos + mn; t[ind] = 2;
int L = 0, R = ind;
for (int i = 1; i < n; i++) {
if (i == ind) continue;
lft.pb(i);
}
sort(all(lft), cmp1);
op.pb(L);
cl.pb(R);
for (auto it : lft) {
// cout << it << endl;
int res1 = getDistance(L, it);
int res2 = getDistance(R, it);
pos = a[L] + res1;
if (pos < a[0]) {
for (auto i : op) {
if (a[i] < pos && res2 == (a[R] - a[i]) + pos - a[i]) {
a[it] = pos;
t[it] = 2;
cl.pb(it);
break;
}
}
}
if (t[it]) continue;
pos = a[R] - res2;
if (pos > a[0]) {
for (auto i : cl) {
if (a[i] > pos && res1 == (a[i] - a[L]) + a[i] - pos) {
a[it] = pos;
t[it] = 1;
op.pb(it);
break;
}
}
}
if (t[it]) continue;
if (dist[0][it] == dist[0][ind] + a[ind] - pos) {
op.pb(it);
t[it] = 1;
a[it] = pos;
L = it;
} else {
cl.pb(it);
t[it] = 2;
a[it] = a[L] + res1;
R = it;
}
}
/**cout << "\nasd\n";
for (int i = 0; i < n; i++) {
cout << i << " ==> " << a[i] << " " << t[i] << endl;
}**/
}
