#include "convex.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
mt19937 rnd(114514);
int gen(int l,int r) {return rnd()%(r-l+1)+l;}
const int INF=1e6+5;
int vis5[INF];
std::vector<int> convex(int n)
{
vector <int> v;
if (query(1,2,3)==-1) {v.pb(1);v.pb(2);v.pb(3);}
else {v.pb(1);v.pb(3);v.pb(2);}
for (int i=4;i<=n;i++) {
int len=v.size();
for (int j=0;j<len;j++) vis5[j]=0;
int l=1,r=len-1,ans=len;
while (l<=r) {
int Mid=(l+r)>>1;
if (query(v[0],v[Mid],i)==1) r=(ans=Mid)-1;
else l=Mid+1;
}
ans--;
int id=ans;
if (query(v[id],v[(id+1)%len],i)==-1) continue;
vis5[id]++;vis5[(id+1)%len]++;
int L=id,R=(id+1)%len;
while (query(v[(L+len-1)%len],v[L],i)==1) L+=len-1,L%=len,vis5[L]++,vis5[(L+1)%len]++;
while (query(v[R],v[(R+1)%len],i)==1) vis5[R]++,vis5[(R+1)%len]++,R++,R%=len;
vector <int> v3;
int fl=1;
for (int j=0;j<len;j++) {
if (vis5[j]<=1) v3.pb(v[j]);
if (vis5[j] && vis5[(j+1)%len]) {if (fl) v3.pb(i);fl=0;}
}
v=v3;
}
reverse(v.begin(),v.end());
return v;
}