#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include "rail.h"
using namespace std;
const int MAX_BLOCS = (1000 * 1000);
int Type[MAX_BLOCS];
pair <int, int> Dist[MAX_BLOCS];
void findLocation(int nbBlocs, int dep, int AnsPosition[], int AnsType[]) {
Type[dep] = 1;
for (int i = 1; i < nbBlocs; i ++)
{
Dist[i] = {getDistance(0, i), i};
}
sort(Dist + 1, Dist + nbBlocs);
AnsPosition[0] = dep;
AnsType[0] = 1;
AnsPosition[Dist[1].second] = dep + Dist[1].first;
Type[AnsPosition[Dist[1].second]] = AnsType[Dist[1].second] = 2;
int gauche = 0, droite = Dist[1].second;
for (int i = 2; i < nbBlocs; i ++)
{
int id = Dist[i].second;
int lA = getDistance(id, droite), lB = getDistance(id, gauche);
int mid = (AnsPosition[gauche] + AnsPosition[droite] - lA + lB) / 2;
if (Type[mid] == 1 || (Type[mid] == 0 && mid > dep))
{
AnsPosition[id] = AnsPosition[gauche] + lB;
Type[AnsPosition[id]] = AnsType[id] = 2;
}
if (Type[mid] == 2 || (Type[mid] == 0 && mid < dep))
{
AnsPosition[id] = AnsPosition[droite] - lA;
Type[AnsPosition[id]] = AnsType[id] = 1;
}
if (AnsPosition[id] < AnsPosition[gauche])
gauche = id;
if (AnsPosition[id] > AnsPosition[droite])
droite = id;
}
return;
}
