#include <bits/stdc++.h>
#include "rail.h"
using namespace std;
int n, s, c;
int a[5002];
int b[5002];
vector<pair<int, int> > vec1, vec2;
int type[3000002];
void findLocation(int N, int first, int location[], int stype[]){
if(N==1){
location[0] = first;
stype[0] = 1;
return;
}
n = N, s = first;
for(int i=1; i<n; i++) a[i] = getDistance(0, i);
c = min_element(a+1, a+n) - a;
for(int i=0; i<n; i++){
if(i!=c){
b[i] = getDistance(c, i);
}
}
location[0] = s;
stype[0] = 1;
type[s] = 1;
location[c] = a[c] + s;
stype[c] = 2;
type[location[c]] = 2;
for(int i=1; i<n; i++){
if(i==c) continue;
if(b[i] < b[0]){
location[i] = location[c] - b[i];
stype[i] = 1;
type[location[i]] = 1;
continue;
}
if(a[i] == a[c] + b[i]) vec2.push_back(make_pair(b[i], i));
else vec1.push_back(make_pair(a[i], i));
}
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
int r = 0;
int rLoc = 0;
for(auto p: vec1){
int x = p.second, dist = p.first;
if(!r){
location[x] = s + dist;
stype[x] = 2;
r = x;
rLoc = s+dist;
type[location[x]] = 2;
continue;
}
int tmp = getDistance(r, x);
int tmp2 = a[r] + tmp - a[x];
// assert(tmp2 >= 0 && type[rLoc - tmp2/2]);
if(type[rLoc - tmp2/2] == 2){
location[x] = rLoc - tmp;
stype[x] = 1;
type[location[x]] = 1;
}
else{
location[x] = s + dist;
stype[x] = 2;
r = x;
rLoc = s + dist;
type[location[x]] = 2;
}
}
s = location[c];
r = 0;
rLoc = 0;
for(auto p: vec2){
int x = p.second, dist = p.first;
if(!r){
location[x] = s - dist;
stype[x] = 1;
r = x;
rLoc = s-dist;
type[location[x]] = 1;
continue;
}
int tmp = getDistance(r, x);
int tmp2 = b[r] + tmp - b[x];
if(type[rLoc + tmp2/2] == 1){
location[x] = rLoc + tmp;
stype[x] = 2;
type[location[x]] = 2;
}
else{
location[x] = s - dist;
stype[x] = 1;
r = x;
rLoc = s - dist;
type[location[x]] = 1;
}
}
}
