#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "swaps.h"
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*vector<int> A;
vector<pair<int, int>> scheduled;
set<int> used;
void schedule(int a, int b) {
pair<int, int> v = {a,b};
if(used.find(v.first)!=used.end() || used.find(v.second)!=used.end()) {
cout << "Reapeted number in schedule\n";
exit(0);
}
used.insert(v.first);
used.insert(v.second);
scheduled.push_back(v);
if(A[v.first] < A[v.second]) swap(A[v.first], A[v.second]);
}
void visit() {
while(scheduled.size()) scheduled.pop_back();
while(used.size()) used.erase(*used.begin());
}
vector<int> r;
void answer(vector<int> R) { r = R; } */
vector<vector<pair<int, int>>> network;
void merge(vector<int> v, int &depth) {
if(v.size()==2) {
network[depth].push_back({v[0], v[1]});
return;
}
vector<int> odd, even;
for(int i=0; i<v.size(); i+=2) odd.push_back(v[i]);
for(int i=1; i<v.size(); i+=2) even.push_back(v[i]);
int old_depth = depth;
merge(odd, depth);
depth = old_depth;
merge(even, depth);
depth++;
for(int i=1; i+1<v.size(); i+=2) {
network[depth].push_back({v[i], v[i+1]});
}
}
void prepareOddEvenBatcherSortingNetwork(int N) {
int base = ceil(log2(double(N)));
int n = 1<<base;
network.resize(base*base);
int sajz = 2;
int depth = 0;
while(sajz <= n) {
for(int l=0; l<n; l+=sajz) {
int r = l+sajz-1;
if(sajz==2) {
network[depth].push_back({l,r});
continue;
}
vector<int> vals;
for(int x=l; x<=r; ++x) vals.push_back(x);
int old = depth;
merge(vals, depth);
if(l+sajz < n) depth = old;
}
depth++;
sajz *= 2;
}
/*for(auto vec : network) {
if(vec.empty()) continue;
for(auto[a,b] : vec) cout << "(" << a << " " << b << ") ";
cout << "\n";
}*/
}
void solve(int N, int V) {
prepareOddEvenBatcherSortingNetwork(N);
for(auto vec : network) {
if(vec.empty()) continue;
for(auto[a,b] : vec) if(a+1<=N && b+1<=N) schedule(b+1,a+1);
visit();
}
vector<int> id;
for(int i=1; i<=N; ++i) id.push_back(i);
answer(id);
}
/*int main() {
int n;
cin >> n;
A.assign(n+1, 0);
for(int i=1; i<=n; ++i) cin >> A[i];
solve(n, 0);
bool ok = 1;
for(int i=0; i<n; ++i) if(r[i] != A[i+1]) ok = 0;
if(ok) cout << "OK\n";
else cout << "ANS\n";
for(int i=1; i<=n; ++i) cout << A[i] << " "; cout << "\n";
}*/
