#include "rail.h"
#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
void findLocation(signed n, signed first, signed location[], signed stype[]){
stype[0] = 1;
location[0] = first;
int loc0[n], locD[n], locC[n];
int firstD, firstC, distD = inf, distC = inf;
for (int i = 0; i < n; i++){
if (i == 0) loc0[i] = 0;
else loc0[i] = getDistance(0, i);
}
// sort by least
for (int i = 0; i < n; i++){
if (i == 0) continue;
if (distD > loc0[i]){
distD = loc0[i];
firstD = i;
}
}
for (int i = 0; i < n; i++){
if (i == firstD) locD[i] = 0;
else locD[i] = getDistance(firstD, i);
}
// sort by least
for (int i = 0; i < n; i++){
if (i == firstD) continue;
if (distC > locD[i]){
distC = locD[i];
firstC = i;
}
}
// find the distances between each station
stype[firstC] = 1;
stype[firstD] = 2;
location[firstD] = location[0] + distD;
location[firstC] = location[firstD] - distC;
// std::cout << "idx: " << firstC << " type: " << stype[firstC] << " location: " << location[firstC] << "\n";
// std::cout << "idx: " << firstD << " type: " << stype[firstD] << " location: " << location[firstD] << "\n";
// find firstSt and lastSt, largest station
int firstSt = 0, lastSt = firstD, mxLoc = location[firstD], mnLoc = location[0];
locC[firstC] = 0;
for (int i = 0; i < n; i++){
if (locD[i] == loc0[i] - distD){
// then its before D
locC[i] = locD[i] + distC;
}
else{
// then its after D
locC[i] = locD[i] - distC;
}
}
std::vector<int> l, r;
std::vector<std::pair<int, int>> C(n), D(n);
for (int i = 0; i < n; i++){
if (i == firstC || i == firstD) continue;
if (locC[i] > locD[i]){
l.push_back(i);
}
else{
r.push_back(i);
}
}
// std::cout << "l: ";
// for (int i: l){
// std::cout << i << ' ';
// }
// std::cout << "\n";
// std::cout << "r: ";
// for (int i: r){
// std::cout << i << ' ';
// }
// std::cout << "\n";
for (int i = 0; i < n; i++){
C[i] = {locC[i], i};
D[i] = {locD[i], i};
}
std::sort(C.begin(), C.end());
std::sort(D.begin(), D.end());
// for (int i = 0; i < n; i++){
// std::cout << C[i].first << ' ' << C[i].second << std::endl;
// }
// for (int i = 0; i < n; i++){
// std::cout << D[i].first << ' ' << D[i].second << std::endl;
// }
int furthestC = firstC;
for (int i = 1; i < n; i++){
int idx = D[i].second, ok = 0;
for (int j: l){
if (idx == j){
ok = 1;
break;
}
}
if (ok){
furthestC = idx;
break;
}
}
// consider left bound
for (int i = 2; i < n; i++){
std::pair<int, int> pa = D[i];
int idx = pa.second, ok = 0;
for (int j: l){
if (idx == j){
ok = 1;
break;
}
}
if (!ok) continue;
int distfromC = getDistance(furthestC, idx);
if (distfromC < pa.first){
stype[idx] = 2;
location[idx] = location[furthestC] + distfromC;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
else{
stype[idx] = 1;
location[idx] = location[firstD] - pa.first;
furthestC = idx;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
}
int furthestD = firstD;
for (int i = 1; i < n; i++){
int idx = C[i].second, ok = 0;
for (int j: r){
if (idx == j){
ok = 1;
break;
}
}
if (ok){
furthestD = idx;
break;
}
}
// consider left bound
for (int i = 2; i < n; i++){
std::pair<int, int> pa = C[i];
int idx = pa.second, ok = 0;
for (int j: r){
if (idx == j){
ok = 1;
break;
}
}
if (!ok) continue;
int distfromD = getDistance(furthestD, idx);
// std::cout << distfromD << "\n";
// std::cout << furthestD << "\n";
if (distfromD < pa.first){
stype[idx] = 1;
location[idx] = location[furthestD] - distfromD;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
else{
stype[idx] = 2;
location[idx] = location[firstC] + pa.first;
furthestD = idx;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
}
}
