#include<bits/stdc++.h>
#include "xylophone.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
const int NN = 1e6+54321, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;
int A[NN], uz[NN];
void solve(int N)
{
int poczatek = -1, koniec = N;
while(koniec - poczatek > 1)
{
int srodek = (poczatek + koniec) / 2;
if(query(srodek+1,N) == N-1) poczatek = srodek;
else koniec = srodek;
}
//cout << "POCZATEK: " << poczatek << endl;
int idx = poczatek;
A[idx] = 1, uz[1] = 1;
if(idx-1 >= 0) A[idx-1] = 1+query(idx-1+1,idx+1), uz[A[idx-1]] = 1;
if(idx+1 < N) A[idx+1] = 1+query(idx+1,idx+2), uz[A[idx+1]] = 1;
for(int i = idx+2; i < N; ++i)
{
int val = query(i-1+1,i+1), lew = A[i-1]-val, praw = A[i-1]+val;
//cout << "I: " << i << " VAL: " << val << " LEW: " << lew << " PRAW: " << praw << endl;
if(lew < 1 or uz[lew]) A[i] = praw, uz[praw] = 1;
else if(praw > N or uz[praw]) A[i] = lew, uz[lew] = 1;
else
{
//cout << "III: " << i << endl;
int que = query(i-2+1,i+1);
if(A[i-2] < lew)
{
//cout << "III: " << i << " QUE: " << que << " ROZ: " << lew-A[i-2] << endl;
if(A[i-2]+que <= A[i-1]) A[i] = lew, uz[lew] = 1;
else A[i] = praw, uz[praw] = 1;
}
else if(A[i-2] > praw)
{
if(A[i-2]-que >= A[i-1]) A[i] = praw, uz[praw] = 1;
else A[i] = lew, uz[lew] = 1;
}
else if(A[i-2] > lew and A[i-2] < A[i-1])
{
if(que > val) A[i] = praw, uz[praw] = 1;
else A[i] = lew, uz[lew] = 1;
}
else
{
if(que > val) A[i] = lew, uz[lew] = 1;
else A[i] = praw, uz[praw] = 1;
}
}
}
//cout << "T" << endl;
//rep(i,N) cout << A[i] << endl;
//cout << endl;
for(int i = idx-2; i >= 0; --i)
{
int val = query(i+1,i+1+1), lew = A[i+1]-val, praw = A[i+1]+val;
//cout << "I: " << i << " VAL: " << val << " LEW: " << lew << " PRAW: " << praw << endl;
if(lew < 1 or uz[lew]) A[i] = praw, uz[praw] = 1;
else if(praw > N or uz[praw]) A[i] = lew, uz[lew] = 1;
else
{
//cout << "III: " << i << endl;
int que = query(i+1,i+2+1);
if(A[i+2] < lew)
{
//cout << "III: " << i << " QUE: " << que << " ROZ: " << lew-A[i-2] << endl;
if(A[i+2]+que <= A[i+1]) A[i] = lew, uz[lew] = 1;
else A[i] = praw, uz[praw] = 1;
}
else if(A[i+2] > praw)
{
if(A[i+2]-que >= A[i+1]) A[i] = praw, uz[praw] = 1;
else A[i] = lew, uz[lew] = 1;
}
else if(A[i+2] > lew and A[i+2] < A[i+1])
{
if(que > val) A[i] = praw, uz[praw] = 1;
else A[i] = lew, uz[lew] = 1;
}
else
{
if(que > val) A[i] = lew, uz[lew] = 1;
else A[i] = praw, uz[praw] = 1;
}
}
}
//cout << "T" << '\n';
//cout << endl;
//rep(i,N) cout << A[i] << endl;
//cout << endl;
rep(i,N) answer(i+1,A[i]);
}
