#include "xylophone.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
static int A[5001];
// On peut avoir pos min en log(N) operations : 13 op
void calcRep(int deb, int fin, bool avant, bool estMin)
{
if (deb > fin) return ;
if (avant)
{
int diffMax = query(deb-1, fin);
if (deb == fin)
{
A[deb] = estMin ? A[deb-1] + diffMax : A[deb-1] - diffMax;
return ;
}
int lo(deb), up(fin);
while (lo < up)
{
int mid = (lo + up) / 2;
if (query(deb-1, mid) == diffMax)
up = mid;
else
lo = mid+1;
}
A[lo] = estMin ? A[deb-1] + diffMax : A[deb-1] - diffMax;
calcRep(deb, lo-1, false, !estMin);
calcRep(lo+1, fin, true, !estMin);
}
else
{
int diffMax = query(deb, fin+1);
if (deb == fin)
{
A[deb] = estMin ? A[deb+1] + diffMax : A[deb+1] - diffMax;
return ;
}
int lo(deb), up(fin);
while (lo < up)
{
int mid = (lo + up + 1) / 2;
if (query(mid, fin+1) == diffMax)
lo = mid;
else
up = mid-1;
}
A[lo] = estMin ? A[fin+1] + diffMax : A[fin+1] - diffMax;
calcRep(deb, lo-1, false, !estMin);
calcRep(lo+1, fin, true, !estMin);
}
}
void solve(signed N)
{
int diffMax = N-1;
int lo(1), up(N);
while (lo < up)
{
int mid = (lo + up+1)/2;
if (query(mid, N) == diffMax)
lo = mid;
else
up = mid-1;
}
int posMin = lo;
A[posMin] = 1;
calcRep(1, posMin-1, false, true);
calcRep(posMin+1, N, true, true);
for (int i(1); i <= N; ++i)
answer(i, A[i]);
}
