#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
struct Val {
int i, val;
};
const int N = 1e4;
int n;
vector<Val> dist;
unordered_map<int, int> id;
void findLocation(int n1, int first, int location[], int stype[]) {
n = n1;
stype[0] = 1;
location[0] = first;
if(n == 1)
return;
for(int i = 1; i < n; i++)
dist.push_back({i, getDistance(0, i)});
sort(dist.begin(), dist.end(),
[](Val a, Val b) {
return a.val < b.val;
});
id[location[0]] = 0;
stype[dist[0].i] = 2;
location[dist[0].i] = first + dist[0].val;
id[location[dist[0].i]] = dist[0].i;
int l = 0, r = dist[0].i;
for(int i = 1; i < n-1; i++) {
int a = getDistance(l, dist[i].i),
b = getDistance(r, dist[i].i),
p = (a - b + location[l] + location[r])/2;
if(id.find(p) == id.end()) {
if(p > first) {
stype[dist[i].i] = 2;
location[dist[i].i] = location[l] + a;
} else {
stype[dist[i].i] = 1;
location[dist[i].i] = location[r] - b;
}
} else {
int j = id[p];
if(stype[j] == 1) {
stype[dist[i].i] = 2;
location[dist[i].i] = location[l] + a;
} else {
stype[dist[i].i] = 1;
location[dist[i].i] = location[r] - b;
}
}
if(stype[dist[i].i] == 1 && location[dist[i].i] < location[l])
l = dist[i].i;
if(stype[dist[i].i] == 2 && location[dist[i].i] > location[r])
r = dist[i].i;
id[location[dist[i].i]] = dist[i].i;
}
}
