#include<bits/stdc++.h>
using namespace std;
#include "rail.h"
#define mp make_pair
#define st first
#define nd second
#define mxx 10004
pair < int , int > T[mxx];
int L[mxx],R[mxx],l,r,El[mxx],Er[mxx],UU[mxx];
void findLocation(int n, int x, int *A, int *B){
int i,j,y,z,u,uu,t,tt,mn;
A[0] = x;
B[0] = 1;
if(n == 1) return;
for(i=1;i<n;i++)
T[i] = mp(abs(getDistance(0,i)),i);
sort(T+1,T+n);
y = T[1].nd;
A[y] = x+T[1].st;
B[y] = 2;
x = 0;
R[0] = y;
L[0] = x;
memset(El,-1,sizeof El);
memset(Er,-1,sizeof Er);
El[0] = A[y];
mn = T[1].st;
for(i=2;i<n;i++){
z = T[i].nd;
UU[i] = abs(getDistance(y,z));
if(mn > UU[i]) mn = UU[i];
}
Er[0] = A[y]-mn;
//cout << x << " " << A[x] << " aa\n";
//cout << y << " " << A[y] << " bb\n";
for(i=2;i<n;i++){
u = T[i].st;
z = T[i].nd;
if(u != T[1].st + (uu=UU[i])){
if(!r){
A[z] = A[x]+u;
B[z] = 2;
R[++r] = z;
continue;
}
t = abs(getDistance(z,R[r]));
for(j=r; j ; j--)
if(Er[j] != -1) break;
//cout << z << " " << R[r] << " " << t << " " << j << " " << Er[0] << " " << A[x]+u-Er[j] + R[r]-Er[j] << " aa\n";
if(t == A[x]+u-Er[j] + A[ R[r] ]-Er[j]){
A[z] = A[x]+u;
B[z] = 2;
R[++r] = z;
continue;
}
int zz=0;
for(j=1;j<=r;j++)
if((tt=A[ R[j] ]-(u-(A[ R[j] ]-A[x]))) > A[ R[j-1] ] && t == A[ R[r] ]-tt){
if(zz) exit(0);
zz = 1;
A[z] = tt;
B[z] = 1;
if(Er[j] == -1) Er[j] = A[z];
//break;
}
if(!zz) assert(0);
}
else{
if(A[y]-uu > A[x]){
A[z] = A[y]-uu;
B[z] = 1;
continue;
}
if(!l){
A[z] = A[y]-uu;
B[z] = 1;
L[++l] = z;
continue;
}
t = abs(getDistance(z,L[l]));
for(j=l; j ; j--)
if(El[j] != -1) break;
if(t == El[j]-(A[y]-uu) + El[j]-A[ L[l] ]){
A[z] = A[y]-uu;
B[z] = 1;
L[++l] = z;
continue;
}
int zz=0;
for(j=1;j<=l;j++)
if((tt=A[ L[j] ]+(uu-(A[y]-A[ L[j] ]))) < A[ L[j-1] ] && t == tt-A[ L[l] ]){
if(zz) exit(0);
zz = 1;
A[z] = tt;
B[z] = 2;
if(El[j] == -1) El[j] = A[z];
//break;
}
if(!zz) assert(0);
}
}
}
