#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool chk[5050];
int n;
bool valid(int v, int x, int* location, int* stype){
if (location[0]<=v) return (v-location[0]==x);
int x1=-1e9, x2=1e9;
for (int i=0;i<n;i++) if (chk[i]){
if (location[i]>location[0] && location[i]<x2 && stype[i]==2) x2 = location[i];
}
for (int i=0;i<n;i++) if (chk[i]){
if (location[i]<v && location[i]>x1 && stype[i]==1) x1 = location[i];
}
return (x2+(x2-x1)+(v-x1))==x;
}
bool valid2(int v, int r, int x, int* location, int* stype){
if (v<=location[r]){
int x2 = -1e9;
for (int i=0;i<n;i++) if (chk[i]){
if (location[i]<v && location[i]>x2 && stype[i]==1) x2 = location[i];
}
return location[r]-x2+(v-x2)==x;
}
int x1=-1e9;
for (int i=0;i<n;i++) if (chk[i]){
if (location[i]<location[r] && location[i]>x1 && stype[i]==1) x1 = location[i];
}
return location[r]-x1+(v-x1)==x;
}
void debug(int* location, int* stype){
for (int i=0;i<n;i++){
if (!chk[i]) printf("X ");
else printf("%d ", location[i]);
}
printf("\n");
for (int i=0;i<n;i++){
if (!chk[i]) printf("X ");
else printf("%d ", stype[i]);
}
printf("\n\n");
}
void findLocation(int N, int first, int location[], int stype[]){
n = N;
vector<pair<int, int>> d;
for (int i=1;i<=N-1;i++) d.emplace_back(getDistance(0, i), i);
sort(d.begin(), d.end());
location[0] = first;
stype[0] = 1;
location[d[0].second] = first+d[0].first;
stype[d[0].second] = 2;
chk[0] = 1, chk[d[0].second] = 1;
//debug(location, stype);
int L = 0, R = d[0].second;
for (int z=1;z<N-1;z++){
int cur = d[z].second, val = d[z].first;
int LD = getDistance(L, cur), RD = getDistance(R, cur);
if (valid(location[L]+LD, val, location, stype) && valid2(location[L]+LD, R, RD, location, stype)){
location[cur] = location[L]+LD, stype[cur] = 2;
if (location[cur]>location[R]) R = cur;
}
else{
location[cur] = location[R]-RD, stype[cur] = 1;
if (location[cur]<location[L]) L = cur;
}
chk[cur] = 1;
//debug(location, stype);
}
}
