#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int a[5005];
int dp[5005][5005];
bool was[5005];
int ask(int l, int r){
if(dp[l][r]) return dp[l][r];
else if(l + 1 == r && was[a[l]] && was[a[l + 1]]) return dp[l][r] = abs(a[l + 1] - a[l]);
else if(l + 2 == r && was[a[l]] && was[a[l + 1]] && was[a[l + 2]]) return dp[l][r] = max({a[l], a[l + 1], a[l + 2]}) - min({a[l], a[l + 1], a[l + 2]});
return dp[l][r] = query(l, r);
}
void solve(int n){
int l = 1, r = n;
while(r - l > 1){
int md = ((l + r) >> 1);
if(ask(1, md) == n - 1) r = md;
else l = md;
}
a[r] = n, was[a[r]] = 1;
a[l] = n - ask(l, r), was[a[l]] = 1;
if(r < n) a[r + 1] = n - ask(r, r + 1), was[a[r + 1]] = 1;
for(int i = l - 1; i >= 1; i--){
a[i] = a[i + 1] - ask(i, i + 1);
if(a[i] < 0 || a[i] > n || was[a[i]]){
a[i] = a[i + 1] + ask(i, i + 1);
was[a[i]] = 1;
continue;
}
if(ask(i, i + 1) == abs(a[i + 1] - a[i])
&& ask(i, i + 2) == max({a[i], a[i + 1], a[i + 2]}) - min({a[i], a[i + 1], a[i + 2]})
&& ask(i + 1, i + 2) == abs(a[i + 2] - a[i + 1])){
was[a[i]] = 1;
continue;
}
a[i] = a[i + 1] + ask(i, i + 1);
was[a[i]] = 1;
}
for(int i = r + 2; i <= n; i++){
a[i] = a[i - 1] - ask(i - 1, i);
if(a[i] < 0 || a[i] > n || was[a[i]]){
a[i] = a[i - 1] + ask(i - 1, i);
was[a[i]] = 1;
continue;
}
if(ask(i - 1, i) == abs(a[i] - a[i - 1])
&& ask(i - 2, i) == max({a[i], a[i - 1], a[i - 2]}) - min({a[i], a[i - 1], a[i - 2]})
&& ask(i - 2, i - 1) == abs(a[i - 2] - a[i - 1])){
was[a[i]] = 1;
continue;
}
a[i] = a[i - 1] + ask(i - 1, i);
was[a[i]] = 1;
}
for(int i = 1; i <= n; i++){
answer(i, a[i]);
}
}
