#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int sp[5002], dist[5002];
bool U[5002];
priority_queue<pair<int, int>> pq;
vector<int> C, D;
void findLocation(int N, int first, int location[], int stype[])
{
for(int i=1;i<N;i++) dist[i] = getDistance(0, i);
for(int i=1;i<N;i++) pq.push({-dist[i], i});
int l = 0, r = pq.top().second;
stype[0] = 1;
stype[r] = 2;
location[0] = first;
location[r] = first - pq.top().first;
C.push_back(location[0]);
D.push_back(location[r]);
pq.pop();
for(int i=2;i<N;i++)
{
int nxt = pq.top().second, d = -pq.top().first;
pq.pop();
int ld = getDistance(l, nxt);
int rd = getDistance(r, nxt);
int rt = 10000000;
for(int j : D) if(max(location[r] - rd, location[0]) < j) rt = min(rt, j);
int sd = 2 * rt - location[0] - (location[r] - rd);
int kt = 10000000;
for(int j : D) if(max(location[r] - rd, location[l]) < j) kt = min(kt, j);
int kd = 2 * kt - location[l] - (location[r] - rd);
if(sd == d && kd == ld)
{
stype[nxt] = 1;
location[nxt] = location[r] - rd;
C.push_back(location[nxt]);
if(location[l] > location[nxt]) l = nxt;
}
else
{
stype[nxt] = 2;
location[nxt] = location[l] + ld;
D.push_back(location[nxt]);
if(location[r] < location[nxt]) r = nxt;
}
}
}
