// ~ Be Name Khoda ~ //
#include "rail.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e3 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int dis[maxn5];
vector <pair<int, int>> av;
void findLocation(int n, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
if(n == 1)
return;
for(int i = 1; i < n; i++){
dis[i] = getDistance(0, i);
av.pb({dis[i], i});
}
sort(all(av));
int lastC = 0, lastD = -1;
for(auto p : av){
int v = p.se;
if(lastD == -1){
lastD = v;
location[v] = location[0] + dis[v];
stype[v] = 2;
continue;
}
int disC = getDistance(lastC, v);
int disD = getDistance(lastD, v);
if(disC + location[lastC] - location[lastD] + 2 * (location[lastD] - location[lastC]) == disD){
location[v] = disC + location[lastC];
lastD = v;
stype[v] = 2;
}
else{
location[v] = location[lastD] - disD;
if(location[v] > location[lastC])
lastC = v;
stype[v] = 1;
}
}
return;
//for(int i = 0; i < n; i++)
//cout << "* " << location[i] << ' ' << stype[i] << endl;
return;
}
