#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;
vector < int > firstGroup, secondGroup, thirdGroup, zeroes;
vector < int > leftNeighbor, rightNeighbor, whichGroup;
void Do(int l, int r, vector<int>&vc, int val = 1){
while( l <= r ) zeroes[vc[l++]] = val;
}
vector < int > FindNeighbors( int l, int r, int x, vector < int> & vc ){
if( l > r ) return {};
if( l == r ) return {vc[l]};
vector < int > res;
int m = (l+r)>>1;
Do(l, m, vc, 1); zeroes[x] = 1;
if( Query(zeroes) <= m-l+1 ){
Do(l, m, vc, 0); zeroes[x] = 0;
vector < int > vv = FindNeighbors(l, m, x, vc);
for( auto c: vv ) res.push_back( c );
}else{
Do(l, m, vc, 0); zeroes[x] = 0;
}
Do(m+1, r, vc, 1); zeroes[x] = 1;
if( Query(zeroes) <= r-m ){
Do(m+1, r, vc, 0); zeroes[x] = 0;
vector < int > vv = FindNeighbors(m+1, r, x, vc);
for( auto c: vv ) res.push_back( c );
}else{
Do(m+1, r, vc, 0); zeroes[x] = 0;
}
return res;
}
vector < int > RestoreBookshelf(int x){
vector < int > res;
if( leftNeighbor[x] != -1 ){
if( leftNeighbor[leftNeighbor[x]] == x )leftNeighbor[leftNeighbor[x]] = -1;
if( rightNeighbor[leftNeighbor[x]] == x ) rightNeighbor[leftNeighbor[x]] = -1;
res = RestoreBookshelf(leftNeighbor[x]);
}
else if( rightNeighbor[x] != -1 ){
if( leftNeighbor[rightNeighbor[x]] == x )leftNeighbor[rightNeighbor[x]] = -1;
if( rightNeighbor[rightNeighbor[x]] == x ) rightNeighbor[rightNeighbor[x]] = -1;
res = RestoreBookshelf(rightNeighbor[x]);
}
res.push_back(x+1);
return res;
}
void Solve(int N)
{
for( int i = 0; i < N; i ++ ){
zeroes.push_back( 0 );
whichGroup.push_back(0);
leftNeighbor.push_back(-1);
rightNeighbor.push_back(-1);
}
vector < int > firstQueryVector(N, 0), secondQueryVector(N,0), thirQueryVector(N,0);
for( int i = 0; i < N; i ++ ){
firstQueryVector[i] = 1;
size_t size = Query(firstQueryVector);
if( size == firstGroup.size()+1 ){
firstGroup.push_back( i );
whichGroup[i] = 1;
}else{
firstQueryVector[i] = 0;
secondQueryVector[i] = 1;
size = Query(secondQueryVector);
if( size == secondGroup.size()+1 ){
secondGroup.push_back(i);
whichGroup[i] = 2;
}else{
secondQueryVector[i] = 0;
thirQueryVector[i] = 1;
thirdGroup.push_back(i);
whichGroup[i] = 3;
}
}
}
for( auto x: firstGroup ){
vector < int > neighbors = FindNeighbors(0, secondGroup.size()-1, x, secondGroup);
//printf("f to s %d ", x);
for( auto neigh: neighbors){
//printf("%d ", neigh);
if( leftNeighbor[x] == -1 )
leftNeighbor[x] = neigh;
else rightNeighbor[x] = neigh;
if( leftNeighbor[neigh] == -1 )
leftNeighbor[neigh] = x;
else rightNeighbor[neigh] = x;
}
//printf("\n");
}
for( auto x: firstGroup ){
vector < int > neighbors = FindNeighbors(0, thirdGroup.size()-1, x, thirdGroup);
//printf("f to th %d ", x);
for( auto neigh: neighbors){
//printf("%d ", neigh);
if( leftNeighbor[x] == -1 )
leftNeighbor[x] = neigh;
else rightNeighbor[x] = neigh;
if( leftNeighbor[neigh] == -1 )
leftNeighbor[neigh] = x;
else rightNeighbor[neigh] = x;
}
//printf("\n");
}
for( auto x: secondGroup ){
vector < int > neighbors = FindNeighbors(0, thirdGroup.size()-1, x, thirdGroup);
//printf("s to th %d ", x);
for( auto neigh:neighbors){
//printf("%d ", neigh);
if( leftNeighbor[x] == -1 )
leftNeighbor[x] = neigh;
else rightNeighbor[x] = neigh;
if( leftNeighbor[neigh] == -1 )
leftNeighbor[neigh] = x;
else rightNeighbor[neigh] = x;
}
//printf("\n");
}
vector < int > bookshelf;
for( int i = 0; i < N; i ++ ){
if( leftNeighbor[i] == -1 || rightNeighbor[i] == -1 ){
bookshelf = RestoreBookshelf(i);
break;
}
}
/*
for( int i = 0; i < N; i ++ ){
printf("%d %d %d\n", i, leftNeighbor[i], rightNeighbor[i] );
}
for( auto c: firstGroup ){
printf("%d ", c);
}printf("\n");
for( auto c: secondGroup ){
printf("%d ", c);
}printf("\n");
for( auto c: bookshelf){
printf("%d ", c);
}
printf("\n");
*/
Answer(bookshelf);
}
