#include "rail.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1000000;
int val[nmax];
void findLocation(int N, int first, int location[], int stype[])
{
int n = N;
array<int, 2> a[n];
for(int i = 0; i < n; i++){
a[i][0] =getDistance(0, i);
a[i][1] = i;
}
sort(a, a + n);
int l = 0, r = a[1][1];
stype[r] = 2;
stype[l] = 1;
//cout << r;
location[r] = first + a[1][0];
location[0] = first;
val[first + a[1][0]] = 2;
val[first] = 1;
for(int i= 2; i < n; i++){
//
int ind = a[i][1];
int d1 = getDistance(l, ind);
int d2 = getDistance(r, ind);
//cout << d1 << ' ' << d2 << "\n";
//cout << location[r] << "\n";
if(location[l] + d1 < location[r]){
int p = location[l] + location[r] - d1 - d2;
if(p % 2 == 0){
p /= 2;
if(val[p] == 1){
location[ind] = location[l] + d1;
val[location[ind]] = 2;
stype[ind] = 2;
continue;
}
}
}
if(location[l] + d1 > location[r]){
int p = location[l] + location[r] + d1 - d2;
if(p % 2 == 0){
p /= 2;
//cout << p << ' ' << val[p] << "\n";
if(val[p] == 1){
location[ind] = location[l] + d1;
val[location[ind]] = 2;
stype[ind] = 2;
r = ind;
continue;
}
}
}
stype[ind] = 1;
location[ind] = location[r] - d2;
// cout << location[ind] << ' ';
val[location[ind]] = 1;
if(location[r] - d2 < location[l])
l = ind;
}
}
