#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;
a[tr] = n;
a[tr-1] = n - get(tr-1,tr);
if(tr<n) a[tr+1] = n - get(tr,tr+1);
for(int i = tr-2;i>=1;i--){
if(a[i]!=0) continue;
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;
}
}
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(a[i]!=0) continue;
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
*/
