#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
int n,all[maxn][maxn],vis[maxn][maxn];
map<int,int>mp;
void findLocation(int N, int first, int location[], int stype[])
{
n=N;
location[0]=first;
stype[0]=1;
mp[first]=0;
if(n==1){
return ;
}
for(int i=0;i<1;i++){
for(int j=i+1;j<n;j++){
all[i][j]=all[j][i]=getDistance(i,j);
}
}
vector<pair<int,int>>v;
for(int i=0;i<n;i++){
v.push_back(make_pair(all[0][i],i));
}
sort(v.begin(),v.end());
stype[v[1].second]=2;
location[v[1].second]=first+all[0][v[1].second];
mp[location[v[1].second]]=v[1].second;
int l=0;
int r=v[1].second;
for(int i=2;i<n;i++){
int u=v[i].second;
int whl=0;
all[u][v[1].second]=all[v[1].second][u]=getDistance(u,v[1].second);
if(l==0){
all[u][v[1].second]=all[v[1].second][u]=getDistance(u,v[1].second);
if(all[u][v[1].second]+all[v[1].second][0]==all[u][0]&&all[u][0]>2*all[0][v[1].second]){
whl=first-(all[u][0]-2*all[0][v[1].second]);
}else{
whl=first+10;
}
}else{
all[u][l]=all[l][u]=getDistance(u,l);
whl=location[l]+(all[u][l]+all[l][0]-all[u][0])/2;
}
if(all[u][v[1].second]+all[v[1].second][0]==all[u][0]&&all[u][0]>2*all[0][v[1].second]){
if(whl>first){
whl=location[v[1].second]-all[u][v[1].second];
}
if(mp.count(whl)==0){
stype[u]=1;
location[u]=first+all[v[1].second][0]*2-all[u][0];
mp[location[u]]=u;
l=u;
continue;
}
int z=mp[whl];
all[u][z]=all[z][u]=getDistance(u,z);
if(all[u][0]==all[z][0]+all[u][z]){
stype[u]=2;
location[u]=location[z]+all[u][z];
mp[location[u]]=u;
continue;
}else{
stype[u]=1;
location[u]=first+all[v[1].second][0]*2-all[u][0];
mp[location[u]]=u;
l=u;
continue;
}
}else{
all[u][r]=all[r][u]=getDistance(u,r);
int whr=location[r]-(all[u][r]+all[r][0]-all[u][0])/2;
if(mp.count(whr)==0){
stype[u]=2;
location[u]=first+all[u][0];
mp[location[u]]=u;
r=u;
continue;
}
int z=mp[whr];
all[u][z]=all[z][u]=getDistance(u,z);
if(all[u][0]==all[z][0]+all[u][z]){
stype[u]=1;
location[u]=location[z]-all[u][z];
mp[location[u]]=u;
continue;
}else{
stype[u]=2;
location[u]=first+all[u][0];
mp[location[u]]=u;
r=u;
continue;
}
}
}
}
