// #include <bits/stdc++.h>
// #include "seq.h"
// #define fr(i,j,k) for(register int i=j;i<=k;++i)
// #define rf(i,j,k) for(register int i=j;i>=k;--i)
// using namespace std;
// const int Maxn=1e5+10;
// int b[Maxn];
// int a[Maxn];
// int n;
// int id[Maxn];
// int id1[Maxn];
// inline void Swap(int x,int y){
// 	swap(a[x],a[y]);
// 	id1[a[x]]=x,id1[a[y]]=y;
// }
// inline void add1(int x,int y){
// 	a[y]+=a[x]/2;
// 	a[x]/=2;
// }
// inline void into(int l,int r){
// 	fr(i,l+1,r-1) add(id1[i],id1[i+1]);add(id1[r],id1[1]);
// 	// fr(i,l+1,r-1) printf("add:%d %d\n",id1[i],id1[i+1]);
// 	// printf("add:%d %d\n",id1[r],id1[1]);
// 	fr(i,l+1,r-1) add1(id1[i],id1[i+1]);add1(id1[r],id1[1]);
// 	fr(i,1,n) id1[a[i]]=i;
// }
// inline void solve(){
// 	answer(1);
// 	fr(i,1,n) b[i]=Get(i);
// 	fr(i,1,n) id[b[i]]=i;
// 	fr(i,1,n) a[i]=i;
// 	fr(i,1,n) id1[a[i]]=i;
// 	// puts("id:");
// 	// fr(i,1,n) printf("%d ",id[i]);
// 	// puts("");
// 	// puts("id1:");
// 	// fr(i,1,n) printf("%d ",id1[i]);
// 	// puts("");
// 	rf(i,n,1){
// 		// printf("** %d %d\n",id[i],i);
// 		while(a[id[i]]!=i) into(1,i);
// 	}
// }
// void SEQ(int N,int M){
// 	n=N;
// 	solve();
// }
// #include <bits/stdc++.h>
// #include "seq.h"
// #define fr(i,j,k) for(register int i=j;i<=k;++i)
// #define rf(i,j,k) for(register int i=j;i>=k;--i)
// using namespace std;
// int n;
// const int Maxn=1e5+10;
// int a[Maxn];
// int id[Maxn];
// inline void Swap(int x,int y){
// 	swap(a[x],a[y]);
// 	id[a[x]]=x;id[a[y]]=y;
// }
// int fa[Maxn];
// vector<pair<int,int> >vc,vc1;
// int pow2[35];
// inline void into(){
// 	fr(i,2,n){
// 		fr(j,0,30){
// 			if(pow2[j]<=i) continue;
// 			fa[j]=pow2[j]-i;
// 			break;
// 		}
// 	}
// }
// int dep[Maxn];
// inline void chk(int x,int y){
// 	int xx,yy;
// 	xx=x,yy=y;
// 	fr(i,1,25){
// 		if(xx%2==0) vc1.push_back(make_pair(id[x],id[y])),yy+=xx/2,xx/=2;
// 		else vc1.push_back(make_pair(id[y],id[x])),xx+=yy/2,yy/=2;
// 		if(xx==y && yy==x) break;
// 	}
// 	Swap(x,y);return;
// }
// inline void getid(int x,int y){
// 	vc1.clear();
// 	if(dep[x]<dep[y]) swap(x,y);
// 	while(dep[x]!=dep[y]){
// 		vc1.push_back(make_pair(x,fa[x]));
// 		chk(x,fa[x]);x=fa[x];
// 	}
// 	while(x!=y){
// 		vc1.push_back(make_pair(x,fa[x]));
// 		vc1.push_back(make_pair(y,fa[y]));
// 		x=fa[x];y=fa[y];
// 	}
// 	for(register int i=vc.size()-2;i>=0;--i) chk(vc[i].first,vc[i].second);
// }
// inline void SEQ(int _n,int M) {
// 	// answer(1);
// 	// n=_n;
// 	// fr(i,1,n) a[i]=Get(i),id[a[i]]=i;
// 	// pow2[0]=1;
// 	// fr(i,1,25) pow2[i]=pow2[i-1]*2;
// 	// fr(i,0,25) pow2[i]++;
// 	// into();
// 	// dep[1]=1;
// 	// fr(i,2,n) dep[i]=dep[fa[i]]+1;
// 	// fr(i,1,n) if(id[i]!=i) getid(i,id[i]);
// // 	reverse(vc.begin(),vc.end());
// // 	for(register int i=0;i<vc.size();++i) add(vc[i].first,vc[i].second);
// }
#include <bits/stdc++.h>
#include "seq.h"
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
using namespace std;
int n;
const int Maxn=1e5+10;
int a[Maxn];
int id[Maxn];
inline void Swap(int x,int y){
	swap(a[x],a[y]);
	id[a[x]]=x;id[a[y]]=y;
}
int fa[Maxn];
vector<pair<int,int> >vc,ans;
vector<int> vc1,vc2;
int pow2[35];
inline void into(){
	fr(i,2,n){
		fr(j,0,30){
			if(pow2[j]<=i) continue;
			fa[i]=pow2[j]-i;
			break;
		}
	}
}
int dep[Maxn];
inline void chk1(int x,int y){
	int xx,yy;
	xx=x,yy=y;
	// cout<<"**"<<x<<' '<<y<<' '<<id[x]<<' '<<id[y]<<endl;
	// ans.push_back(make_pair(x,y));
	fr(i,1,25){
		if(xx%2==0) vc.push_back(make_pair(id[x],id[y])),yy+=xx/2,xx/=2;
		else vc.push_back(make_pair(id[y],id[x])),xx+=yy/2,yy/=2;
		if(xx==y && yy==x) break;
	}
	Swap(id[x],id[y]);return;
}
inline void chk(int x,int y){
	int xx,yy;
	xx=x,yy=y;
	// cout<<"**"<<x<<' '<<y<<endl;
	ans.push_back(make_pair(x,y));
	// fr(i,1,25){
	// 	if(xx%2==0) vc.push_back(make_pair(id[x],id[y])),yy+=xx/2,xx/=2;
	// 	else vc.push_back(make_pair(id[y],id[x])),xx+=yy/2,yy/=2;
	// 	if(xx==y && yy==x) break;
	// }
	Swap(id[x],id[y]);return;
}
inline void out(){
	puts("qaq:");
	fr(i,1,n) cout<<i<<' ';
	cout<<endl;
	fr(i,1,n) cout<<id[i]<<' ';
	cout<<endl;
	puts("qwq");
}
inline void getid(int x,int y){
	// cout<<"***"<<x<<' '<<y<<endl;
	vc1.clear();vc2.clear();
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]!=dep[y]){
		vc1.push_back(x);
		x=fa[x];
	}
	while(x!=y){
		vc1.push_back(x);
		vc2.push_back(y);
		x=fa[x];y=fa[y];
	}
	vc2.push_back(x);
	reverse(vc2.begin(),vc2.end());
	for(register int i=0;i<vc2.size();++i) vc1.push_back(vc2[i]);
	// cout<<vc1.size()<<endl;
	if(vc1.size()==2){
		chk(vc1[0],vc1[1]);
		return;
	}
	for(register int i=1;i<vc1.size();++i) chk(vc1[0],vc1[i]),swap(vc1[0],vc1[i]);
	for(register int i=vc1.size()-2;i>=1;--i) chk(vc1[vc1.size()-1],vc1[i]),swap(vc1[vc1.size()-1],vc1[i]);
	// cout<<vc1.size()<<endl;
	// if(vc1.size()>=2) for(register int i=vc1.size()-2;i>=0;--i) cout<<vc1[i].first<<' '<<vc1[i].second<<endl;
	// if(vc1.size()>=2) for(register int i=vc1.size()-2;i>=0;--i) chk(vc1[i].first,vc1[i].second);
	// out();
}
void SEQ(int _n,int M) {
	n=_n;
	fr(i,1,n) a[i]=Get(i),id[a[i]]=i;
	pow2[0]=1;
	fr(i,1,25) pow2[i]=pow2[i-1]*2;
	fr(i,0,25) pow2[i]++;
	// fr(i,1,25) cout<<i<<' '<<pow2[i]<<endl;
	into();
	dep[1]=1;
	fr(i,2,n) dep[i]=dep[fa[i]]+1;
	// fr(i,1,n) cout<<i<<' '<<fa[i]<<endl;
	// fr(i,1,n) cout<<i<<' '<<id[i]<<endl;
	fr(i,1,n) if(id[i]!=i) getid(a[i],a[id[i]]);
	reverse(ans.begin(),ans.end());
	fr(i,1,n) a[i]=i,id[a[i]]=i;
	// cout<<ans.size()<<endl;
	// for(register int i=0;i<ans.size();++i) cout<<ans[i].first<<' '<<ans[i].second<<endl;
	for(register int i=0;i<ans.size();++i) chk1(ans[i].first,ans[i].second);
	answer(1);
	// cout<<vc.size()<<endl;
	// for(register int i=0;i<vc.size();++i) cout<<vc[i].first<<' '<<vc[i].second<<endl;
	for(register int i=0;i<vc.size();++i) add(vc[i].first,vc[i].second);
}