#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int m[5009][5009], A[5009], D[5009];
int get(int s, int t) {
if(s == t) return 0;
if(m[s][t] == -1) m[s][t] = query(s, t);
return m[s][t];
}
void solve(int N) {
memset(m, -1, sizeof(m));
A[1] = 0; A[2] = get(1, 2);
bool inc = 1;
for(int i=3; i<=N; i++) {
if(inc) {
if(get(i-2, i-1) == get(i-2, i)) A[i] = A[i-1] - get(i-1, i), inc = 0;
else {
if(A[i-2] + get(i-2, i) == A[i-1] + get(i-1, i)) A[i] = A[i-1] + get(i-1, i);
else A[i] = A[i-1] - get(i-1, i), inc = 0;
}
}
else {
if(get(i-2, i-1) == get(i-2, i)) A[i] = A[i-1] + get(i-1, i), inc = 1;
else {
if(A[i-2] - get(i-2, i) == A[i-1] - get(i-1, i)) A[i] = A[i-1] - get(i-1, i);
else A[i] = A[i-1] + get(i-1, i), inc = 1;
}
}
}
int mn = 1, mx = 1;
for(int i=1; i<=N; i++) {
if(A[mn] > A[i]) mn = i;
if(A[mx] < A[i]) mx = i;
D[i] = A[i] - A[i-1];
}
if(mn > mx) {
for(int i=2, s=0; i<=N; i++) s += -D[i], A[i] = s;
swap(mn, mx);
}
for(int i=1; i<=N; i++) answer(i, A[i] - A[mn] + 1);
}
