//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include <xylophone.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 5e3;
int res[N + 1];
void solve(int n)
{
int low = 1, high = n;
while(low <= high)
{
int mid = (low + high)/2;
if (query(mid, n) == n - 1)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
res[high] = 1;
if (high < n)
{
res[high + 1] = 1 + query(high, high + 1);
for (int i = high + 2; i <= n; ++ i)
{
int a = query(i - 2, i), b = query(i - 1, i);
if (res[i - 1] > res[i - 2])
{
if (res[i - 1] + b == a + res[i - 2])
{
res[i] = res[i - 1] + b;
}
else
{
res[i] = res[i - 1] - b;
}
}
else
{
if (res[i - 2] - a == res[i - 1] - b)
{
res[i] = res[i - 1] - b;
}
else
{
res[i] = res[i - 1] + b;
}
}
}
}
if (high > 1)
{
res[high - 1] = 1 + query(high - 1, high);
for (int i = high - 2; i >= 1; -- i)
{
int a = query(i, i + 2), b = query(i, i + 1);
if (res[i + 2] > res[i + 1])
{
if (res[i + 1] - b == res[i + 2] - a)
{
res[i] = res[i + 1] - b;
}
else
{
res[i] = res[i + 1] + b;
}
}
else
{
if (res[i + 1] + b == res[i + 2] + a)
{
res[i] = res[i + 1] + b;
}
else
{
res[i] = res[i + 1] - b;
}
}
}
}
for (int i = 1; i <= n; ++ i)
{
answer(i, res[i]);
}
}
/*void read()
{
}
void solve()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}*/
