#include<bits/stdc++.h>
#include "rail.h"
#define MAXN 1000007
using namespace std;
int n,pos;
pair<int,int> block[MAXN];
pair<int,int> dist[5007];
int last;
vector<int> clos;
int sum[MAXN];
void findLocation(int N, int first, int location[], int stype[]){
n=N;
block[first]={0,0};
location[0]=first;
stype[0]=1;
for(int i=1;i<n;i++){
dist[i].first=getDistance(0,i);
dist[i].second=i;
}
sort(dist+1,dist+n);
last=1;
location[dist[1].second]=first+dist[1].first;
stype[dist[1].second]=2;
clos.push_back(1);
for(int i=2;i<n;i++){
bool ok=true;
for(int f:clos){
if(dist[f].first+getDistance(dist[f].second,dist[i].second)==dist[i].first){
ok=false; break;
}
}
if(ok){
clos.push_back(i);
last=i;
stype[dist[i].second]=2;
location[dist[i].second]=first+dist[i].first;
}
}
int special=dist[last].second;
int fin=location[special];
for(int i=0;i<n;i++){
dist[i].first=getDistance(special,i);
dist[i].second=i;
}
sort(dist,dist+n);
last=1;
location[dist[1].second]=fin-dist[1].first;
stype[dist[1].second]=1;
clos={1};
for(int i=2;i<n;i++){
//cout<<"checking "<<dist[i].second<<"\n";
bool ok=true;
int curr=getDistance(dist[last].second,dist[i].second);
int where=location[dist[last].second]+curr;
int nearest=last;
for(int f:clos){
if(location[dist[f].second]<=where and location[dist[f].second]>location[dist[nearest].second])nearest=f;
}
if(dist[i].first == dist[nearest].first + (where-location[dist[nearest].second])){
stype[dist[i].second]=2;
location[dist[i].second]=where;
//cout<<"its backward\n";
continue;
}
if(ok){
//cout<<"new last\n";
last=i;
stype[dist[i].second]=1;
location[dist[i].second]=fin-dist[i].first;
clos.push_back(i);
}
}
return;
}
/*
3
8
1 0
2 2
1 3
2 5
2 6
1 7
1 8
2 10
*/
