#include "xylophone.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
static int A[5000];
#define maxn 5005
int a[maxn];
map<pii,int> mp;
int get(int l,int r){
if(mp.count({l,r})) return mp[{l,r}];
return mp[{l,r}] = query(l,r);
}
void solve(int N) {
int n = N;
int l = 1,r = n,mid,rez;
while(l<=r){
mid = (l+r)/2;
int e = get(1,mid);
if(e<n-1){
l = mid+1;
}else{
r = mid-1;
rez = mid;
}
}
int tr = rez;
l = 1,r = tr-1,mid,rez = -1;
while(l<=r){
mid = (l+r)/2;
if(get(mid,tr)<n-1){
r = mid-1;
}else{
l = mid+1;
rez = mid;
}
}
int tl = rez;
a[tl] = 1;
a[tr] = n;
//cerr<<tl<< " "<<tr<<endl;
if(tl>1) a[tl-1] = 1 + query(tl-1,tl);
for(int i = tl-2;i>=1;i--){
int x = get(i,i+1);
int y = get(i+1,i+2);
int z = get(i,i+2);
if(x+y==z){
if(a[i+1]>=a[i+2]) a[i] = a[i+2] + z;
else a[i] = a[i+2] - z;
}else if(z==x){
if(a[i+1]>=a[i+2]) a[i] = a[i+1] - x;
else a[i] = a[i+1] + x;
}else{
if(a[i+1]>=a[i+2]) a[i] = a[i+1] - x;
else a[i] = a[i+1] + x;
}
}
if(tl<n&&tl+1!=tr) a[tl+1] = a[tl] + query(tl,tl+1);
for(int i = tl+2;i<tr;i++){
int x = get(i-1,i);
int y = get(i-2,i-1);
int z = get(i-2,i);
//cerr<<x<< " "<<y<<" "<<z<<endl;
if(x+y==z){
if(a[i-1]>=a[i-2]) a[i] = a[i-2] + z;
else a[i] = a[i-2] - z;
}else if(z==x){
if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
else a[i] = a[i-1] + x;
}else{
if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
else a[i] = a[i-1] + x;
}
}
if(tr<n) a[tr+1] = a[tr] - query(tr,tr+1);
for(int i = tr+2;i<=n;i++){
int x = get(i-1,i);
int y = get(i-2,i-1);
int z = get(i-2,i);
if(x+y==z){
if(a[i-1]>=a[i-2]) a[i] = a[i-2] + z;
else a[i] = a[i-2] - z;
}else if(z==x){
if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
else a[i] = a[i-1] + x;
}else{
if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
else a[i] = a[i-1] + x;
}
}
//ceri(a,1,n);
for(int i = 1;i<=n;i++) answer(i,a[i]);
}
/*
5
2 1 5 3 4
*/
