#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=1e5+50;
const ll mod=1e9+7 ;
const ll base=1e9;
/// have a medal in APIO
/// goal 6/7
ll res[maxn];
bool chk(vector<ll> vt,ll mx,ll n)
{
ll h=base;
ll h1=-1;
for (auto to:vt)
{
if (to>=1&&to<=n)
{
h1=max(h1,to);
h=min(h,to);
}
else
{
return false;
}
}
if (h1-h!=mx)
return false;
return true;
}
void solve(ll n)
{
ll l=1, h=n;
while (l<=h)
{
ll mid=(l+h)/2;
if (query(mid,n)!=n-1)
h=mid-1;
else
l=mid+1;
}
ll p=h;
res[p]=1;
if (p>1)
{
res[p-1]=query(p-1,p)+1;
}
for (int i=p-2; i>=1; i--)
{
ll h=query(i,i+1);
vector<ll> vt;
vt.pb(res[i+1]-h);
vt.pb(res[i+1]+h);
vector<ll> vt2;
for (auto to:vt)
{
vector<ll> vt1;
vt1.pb(to);
vt1.pb(res[i+1]);
if (chk(vt1,h,n))
{
vt2.pb(to);
}
}
if (vt2.size()==2)
{
ll h=query(i,i+2);
vt.clear();
for (auto to:vt2)
{
vector<ll> vt1;
vt1.pb(to);
vt1.pb(res[i+1]);
vt1.pb(res[i+2]);
if (chk(vt1,h,n))
{
vt.pb(to);
}
}
assert(vt.size()==1);
res[i]=vt.back();
}
else
{
res[i]=vt2.back();
}
}
if (p<n)
{
res[p+1]=query(p,p+1)+1;
}
for (int i=p+2; i<=n; i++)
{
ll h=query(i-1,i);
vector<ll> vt;
vt.pb(res[i-1]-h);
vt.pb(res[i-1]+h);
vector<ll> vt2;
for (auto to:vt)
{
vector<ll> vt1;
vt1.pb(to);
vt1.pb(res[i-1]);
if (chk(vt1,h,n))
{
vt2.pb(to);
}
}
if (vt2.size()==2)
{
ll h=query(i-2,i);
vt.clear();
for (auto to:vt2)
{
vector<ll> vt1;
vt1.pb(to);
vt1.pb(res[i-1]);
vt1.pb(res[i-2]);
if (chk(vt1,h,n))
{
vt.pb(to);
}
}
assert(vt.size()==1);
res[i]=vt.back();
}
else
{
res[i]=vt2.back();
}
}
for (int i=1;i<=n;i++)
{
answer(i,res[i]);
}
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("CONVEXHULL.inp", "r"))
{
freopen("CONVEXHULL.inp", "r", stdin);
freopen("CONVEXHULL.out", "w", stdout);
}
}*/
