#include<bits/stdc++.h>
#include "perm.h"
using namespace std;
vector<int> construct_permutation(long long k){
	vector<int> val(65),flag(65);
	int n=__lg(k),id=1,p1=-1,p2=-1;
	for(int i=n-1;i>=0;i--){
		if(k>>i&1){
			if(i&&(k>>(i-1)&1)&&p1!=-1&&p2!=-1){
				val[p1]--,val[p2]--,val[n-i+1]=val[p2]+1,flag[n-i+1]=1;
				i--,id--;
			}else{
				val[n-i]=--id,flag[n-i]=1;
				p2=p1,p1=n-i;
			}
		}
	}
	vector<int> res;
	for(int i=1;i<=n;i++){
		res.emplace_back(i);
		if(flag[i]) res.emplace_back(val[i]);
	}
	int minn=2e9;
	for(auto v:res) minn=min(minn,v);
	for(auto &v:res) v-=minn;
	return res;
}