#include "rail.h"
#include <bits/stdc++.h>
#define ii pair < int , int >
#define se second
#define fi first
using namespace std;
const int N=5e3+55;
int dist[N];
ii a[N];
void findLocation(int n, int zero, int location[], int stype[])
{
location[0]=zero;
stype[0]=1;
int temp;
for(int i=1;i<n;i++)
{
temp=getDistance(0,i);
a[i-1]={temp,i};
dist[i]=temp;
}
sort(a,a+n-1);
int first;
int second=-1;
int last;
int x,y;
for(int i=0;i<n-1;i++)
{
if(!i)
{
first=a[i].se;
last=first;
location[first]=zero+a[i].fi;
stype[first]=2;
continue ;
}
x=getDistance(last,a[i].se);
// if(first!=last)
// y=getDistance(first,a[i].se);
// cout<<a[i].se<<' '<<a[i].fi<<' '<<dist[first]<<' '<<y<<endl;
if(x+dist[last]==dist[a[i].se])
{
if(last==first)
if(dist[last]<x)
second=a[i].se;
stype[a[i].se]=1;
location[a[i].se]=location[last]-x;
}
else if(x==dist[a[i].se]+dist[last])
{
last=a[i].se;
stype[a[i].se]=2;
location[a[i].se]=zero+a[i].fi;
}
else
{
if(second!=-1)
{
y=getDistance(second,a[i].se);
if(dist[second]+y==a[i].fi)
{
stype[a[i].se]=2;
location[a[i].se]=location[second]+y;
continue ;
}
}
second=a[i].se;
stype[a[i].se]=1;
location[a[i].se]=zero-a[i].fi+2*dist[first];
}
}
// cout<<endl;
// for(int i=0;i<n;i++)
// cout<<stype[i]<<' '<<location[i]<<endl;
}
