#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=5e3+5;
int d1[nx], d2[nx], v1[nx], v2[nx];
bool ad[nx], ad2[nx];
void solve(int N) {
for (int i=1; i<N; i++) d1[i]=query(i, i+1);
for (int i=1; i<N-1; i++) d2[i]=query(i, i+2);
v1[2]=d1[1]; ad[1]=1;
pair<int, int> mn={0, 1}, mx={d1[1], 2};
for (int i=3; i<=N; i++)
{
if (d2[i-2]==d1[i-2]+d1[i-1])
{
if (ad[i-2]) v1[i]=v1[i-1]+d1[i-1], ad[i-1]=1;
else v1[i]=v1[i-1]-d1[i-1], ad[i-1]=0;
}
else
{
if (ad[i-2]) v1[i]=v1[i-1]-d1[i-1], ad[i-1]=0;
else v1[i]=v1[i-1]+d1[i-1], ad[i-1]=1;
}
mn=min(mn, {v1[i], i});
mx=max(mx, {v1[i], i});
}
v2[2]=-d1[1]; ad2[1]=0;
for (int i=3; i<=N; i++)
{
if (d2[i-2]==d1[i-2]+d1[i-1])
{
if (ad2[i-2]) v2[i]=v2[i-1]+d1[i-1], ad2[i-1]=1;
else v2[i]=v2[i-1]-d1[i-1], ad2[i-1]=0;
}
else
{
if (ad2[i-2]) v2[i]=v2[i-1]-d1[i-1], ad2[i-1]=0;
else v2[i]=v2[i-1]+d1[i-1], ad2[i-1]=1;
}
}
if (mn.second<mx.second) for (int i=1; i<=N; i++) answer(i, v1[i]-mn.first+1);
else for (int i=1; i<=N; i++) answer(i, v2[i]+mx.first+1);
}
