#include<bits/stdc++.h>
#include "xylophone.h"
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 5000 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int res[maxN];
void solve(int n)
{
int low = 1, high = n, mid;
while(low <= high)
{
mid = (low + high) / 2;
if(query(mid, n) == n - 1) low = mid + 1;
else high = mid -1;
}
low--;
res[low] = 1;
//cout << query(1, 2);exit(0);
if(low > 1)
{
res[low - 1] = 1 + query(low - 1, low);
}
if(low < n) res[low + 1] = 1 + query(low, low + 1);
for(int i=low-2; i>=1; i--)
{
int val1 = query(i, i + 1);
int val2 = query(i, i + 2);
if(res[i + 1] > res[i + 2])
{
if(res[i + 1] - res[i + 2] == val2)
{
res[i] = res[i + 1] - val1;
}
else
{
int val = res[i + 2] + val2;
if(val - res[i + 1] == val1) res[i] = val;
else res[i] = res[i + 1] - val2;
}
}
else
{
if(res[i + 2] - res[i + 1] == val2)
{
res[i] = res[i + 1] + val1;
}
else
{
int val = res[i + 2] - val2;
if(res[i + 1] - val == val1) res[i] = val;
else res[i] = res[i + 1] + val2;
}
}
}
for(int i=low+2; i<=n; i++)
{
int val1 = query(i - 1, i);
int val2 = query(i - 2, i);
if(res[i - 1] > res[i - 2])
{
if(res[i - 1] - res[i - 2] == val2)
{
res[i] = res[i - 1] - val1;
}
else
{
int val = res[i - 2] + val2;
if(val - res[i - 1] == val1) res[i] = val;
else res[i] = res[i - 1] - val2;
}
}
else
{
if(res[i - 2] - res[i - 1] == val2)
{
res[i] = res[i - 1] + val1;
}
else
{
int val = res[i - 2] - val2;
if(res[i - 1] - val == val1) res[i] = val;
else res[i] = res[i - 1] + val2;
}
}
}
for(int i=1; i<=n; i++) answer(i, res[i]);
}
