在 $i\bmod n=j$ 的时刻问一个点状态显然可以知道它在排列中出现位置是否 $\le j$。

考虑对于每个数维护一个可能出现区间 $[l,r]$，你可以在模 $n$ 后为中点的时刻询问以将区间砍半。

所以每轮开始前给每个区间寻找里中点最近的无安排点即可。

当然过不去，搞点剪枝，考虑让区间长的优先放，让它们问的位置离中点更近，然后把已经确定的点占据的询问位置丢掉，换成其他区间填进去问。

每次 check 是一个类似拓扑排序的过程，一个位置只被一个区间覆盖说明这个区间对应的点就是放这个位置的，可以瞎几把 $O(n\log n)$ 维护，放完了就说明确定了。

注意上述过程中确认了的点一定是确定了位置的，要丢掉减少常数。

期望交互次数 $O(n\log n)$，加上上述常数优化后随便过。

代码：

#include<bits/stdc++.h>
#define ll long long
#define un unsigned
#define INF 214748364719260817
#include <vector>
int press_button(int);
using namespace std;
ll n;
ll l[10005],r[10005];
ll sum[10005];
bool use[10005];
struct px
{
	ll minn,where;
	bool operator<(const px&b)const
	{
		return minn<b.minn;
	}
	px operator+(const ll&b)const
	{
		return (px){b+minn,where};
	}
}tr[40005];
ll tag[40005];
queue<ll>s[40005];
#define ls(id) id*2
#define rs(id) id*2+1
void pushup(ll id)
{
	tr[id]=min(tr[ls(id)],tr[rs(id)])+tag[id];
}
void build(ll id,ll l,ll r)
{
	queue<ll>().swap(s[id]);tag[id]=0;
	if(l==r)
	{
		tr[id].minn=sum[l];tr[id].where=l;
		return;
	}
	ll mid=l+r>>1;
	build(ls(id),l,mid);
	build(rs(id),1+mid,r);
	tr[id]=min(tr[ls(id)],tr[rs(id)]);
}
void ins(ll id,ll l,ll r,ll ml,ll mr,ll val)
{
	if(ml<=l&&r<=mr)
	{
		s[id].emplace(val);return;
	}
	ll mid=l+r>>1;
	if(ml<=mid)ins(ls(id),l,mid,ml,mr,val);
	if(mr>mid)ins(rs(id),1+mid,r,ml,mr,val);
}
ll find(ll id,ll l,ll r,ll ml)
{
	while(!s[id].empty()&&use[s[id].front()])s[id].pop();
	if(l==r)
	{
		tr[id].minn=19260817;return(!s[id].empty()?s[id].front():-1);
	}
	ll mid=l+r>>1,fv;
	if(ml<=mid)fv=find(ls(id),l,mid,ml);
	else fv=find(rs(id),mid+1,r,ml);
	if(!s[id].empty())fv=s[id].front();
	pushup(id);
	return fv;
}
void update(ll id,ll l,ll r,ll ml,ll mr)
{
	if(ml<=l&&r<=mr)
	{
		--tag[id];--tr[id].minn;return;
	}
	ll mid=l+r>>1;
	if(ml<=mid)update(ls(id),l,mid,ml,mr);
	if(mr>mid)update(rs(id),1+mid,r,ml,mr);
	pushup(id);
}
ll np[10005];
bool check()
{
	memset(sum,0,sizeof(sum));
	for(ll i=0;i<n;++i)++sum[l[i]],--sum[r[i]+1],use[i]=0;
	for(ll i=1;i<n;++i)sum[i]+=sum[i-1];
	build(1,0,n-1);
	for(ll i=0;i<n;++i)ins(1,0,n-1,l[i],r[i],i);
	ll cot=0;
	while(tr[1].minn==1)
	{
		++cot;
		ll u=tr[1].where;
		ll e=find(1,0,n-1,u);
		assert(e!=-1);
		use[e]=1;
		np[u]=e;
		update(1,0,n-1,l[e],r[e]);
		l[e]=r[e]=u;
	}
	return cot==n;
}
random_device my;
mt19937 rd(my());
ll id[10005],fw[10005];
bool cmp(ll a,ll b)
{
	return r[a]-l[a]>r[b]-l[b];
}
bool bv[10005];
std::vector<int> solve(int N)
{
	n=N;
	for(ll i=0;i<n;++i)l[i]=0,r[i]=n-1,fw[i]=i,bv[i]=1;
	ll fv=1,kkk=0;
	while(!check())
	{
		++kkk;
		for(ll i=0;i<n;++i)
		{
			while(l[i]!=r[i]&&np[l[i]])++l[i];
			while(l[i]!=r[i]&&np[r[i]])--r[i];
		}
		memset(id,-1,sizeof(id));
		shuffle(fw,fw+n,rd);
		sort(fw,fw+n,cmp);
		set<pair<ll,ll>>s;
		for(ll i=0;i<n;++i)
		{
			ll mid=l[fw[i]]+r[fw[i]]>>1;
			for(ll len=0;;++len)
			{
				if(rd()%2)
				{
					if(mid-len>=0&&-1==id[mid-len])
					{
						id[mid-len]=fw[i];
						break;
					}
					if(mid+len<n&&-1==id[mid+len])
					{
						id[mid+len]=fw[i];
						break;
					}
				}
				else
				{
					if(mid+len<n&&-1==id[mid+len])
					{
						id[mid+len]=fw[i];
						break;
					}
					if(mid-len>=0&&-1==id[mid-len])
					{
						id[mid-len]=fw[i];
						break;
					}	
				}
			}
			if(l[fw[i]]!=r[fw[i]])s.insert(make_pair(mid,fw[i]));
		}
		for(ll i=0;i<n&&s.size();++i)
		{
			if(l[id[i]]==r[id[i]]||i<l[id[i]]||i>r[id[i]])
			{
				auto a=s.lower_bound(make_pair(i,0));
				if(a!=s.end())
				{
					if(a!=s.begin())
					{
						--a;
						auto b=a;
						++a;
						if(a->first-i<i-b->first)id[i]=a->second;
						else if(a->first-i==i-b->first&&rd()%2)id[i]=a->second;
						else id[i]=b->second;
					}
				}
				else
				{
					--a;
					id[i]=a->second;
				}
			}
			if(l[id[i]]!=r[id[i]])
			s.erase(s.find(make_pair(l[id[i]]+r[id[i]]>>1,id[i])));
			if(press_button(id[i])==fv)
			r[id[i]]=min(r[id[i]],i);
			else l[id[i]]=max(l[id[i]],i+1);
			if(l[id[i]]!=r[id[i]])
			s.insert(make_pair(l[id[i]]+r[id[i]]>>1,id[i]));
			bv[i]^=1;
		}
		fv^=1;
	}
	vector<int>p;
	for(ll i=0;i<n;++i)p.emplace_back(np[i]);
	return p;
}
//ll ls[10005];
//bool lt[10005];
//ll cnt;
//int press_button(int x)
//{
//	lt[ls[cnt]]^=1;
//	cnt=(cnt+1)%n;
//	return lt[x];
//}
//int main()
//{
//	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//	cin>>n;
//	for(ll i=0;i<n;++i)cin>>ls[i];
//	solve(n);
//}