#include <iostream>
#include <vector>
#include "xylophone.h"
using namespace std;
/*
13 queries to find pos(N)
1 query for pos(N)+1
For i = pos(N)+2 .. N:
query(i-1, i)
query(i-2, i)
Figure out i
Do the same for i = 1..pos(1)-2
For pos(1) < i < pos(N):
*/
// ----------------------------------------------------------------------------
int n;
int searchN(int a, int b)
{
// debug("searchN", a, b);
if(a == b) return a;
int m = (a+b)/2;
if(query(1, m) == n-1) return searchN(a, m);
else return searchN(m+1, b);
}
vector<int> pos(5001, 0);
vector<int> A(5001, 0);
bool occ(int a) //occupied?
{
return (a < 1) || (n < a) || (pos[a] != 0);
}
void assign(int p, int a)
{
pos[a] = p;
A[p] = a;
answer(p, a);
}
void solve(int N)
{
// debug(111);
n = N;
assign( searchN(2, N), N );
//after N
if(pos[N] < N)
{
assign(pos[N] + 1, N - query(pos[N], pos[N] + 1));
}
// debug(555);
for(int i = pos[N]+2; i <= N; i++)
{
// debug(i);
int X1 = query(i-1, i);
if(occ(A[i-1] + X1)) assign(i, A[i-1] - X1);
else if(occ(A[i-1] - X1)) assign(i, A[i-1] + X1);
else
{
int X2 = query(i-2, i);
if(X2 == abs(A[i-1] - A[i-2]))
{
if(A[i-2] < A[i-1])
{
//A[i-2] < A[i] < A[i-1]
assign(i, A[i-1] - X1);
}
else
{
//A[i-1] < A[i] < A[i-2]
assign(i, A[i-1] + X1);
}
}
else
{
if(A[i-2] < A[i-1] && X1 > X2)
{
//A[i] < A[i-2] < A[i-1]
assign(i, A[i-1] - X1);
}
else if(A[i-2] < A[i-1] && X1 < X2)
{
//A[i-2] < A[i-1] < A[i]
assign(i, A[i-1] + X1);
}
else if(A[i-1] < A[i-2] && X1 > X2)
{
//A[i-1] < A[i-2] < A[i]
assign(i, A[i-1] + X1);
}
else //if(A[i-1] < A[i-2] && X1 < X2)
{
//A[i] < A[i-1] < A[i-2]
assign(i, A[i-1] - X1);
}
}
}
}
assign(pos[N] - 1, N - query(pos[N] - 1, pos[N]));
for(int i = pos[N]-2; i >= 1; i--)
{
// debug(i);
int X1 = query(i, i+1);
if(occ(A[i+1] + X1)) assign(i, A[i+1] - X1);
else if(occ(A[i+1] - X1)) assign(i, A[i+1] + X1);
else
{
int X2 = query(i, i+2);
if(X2 == abs(A[i+1] - A[i+2]))
{
if(A[i+2] < A[i+1])
{
//A[i-2] < A[i] < A[i-1]
assign(i, A[i+1] - X1);
}
else
{
//A[i-1] < A[i] < A[i-2]
assign(i, A[i+1] + X1);
}
}
else
{
if(A[i+2] < A[i+1] && X1 > X2)
{
//A[i] < A[i-2] < A[i-1]
assign(i, A[i+1] - X1);
}
else if(A[i+2] < A[i+1] && X1 < X2)
{
//A[i-2] < A[i-1] < A[i]
assign(i, A[i+1] + X1);
}
else if(A[i+1] < A[i+2] && X1 > X2)
{
//A[i-1] < A[i-2] < A[i]
assign(i, A[i+1] + X1);
}
else //if(A[i-1] < A[i-2] && X1 < X2)
{
//A[i] < A[i-1] < A[i-2]
assign(i, A[i+1] - X1);
}
}
}
}
}
