下文中的 $add(i,j)$ 表示做一次操作。

首先看保证 $b_1=n,b_n=1$，$\forall 1 < i < n ,b_i=i$ 时怎么做，也就是交换 $n$ 和 $1$。如果有 $n=2^k$ 那就直接不停操作 $add(n,1)$ 就做完了；如果 $n \not = 2^k$ ，我们仿照上述思路，先将 $a_n$ 凑成 $2^k$，再把所有其他操作过的数还原回去。

我们记 $a_n$ 的当前值为 $x$，那么我们每次找出 $x$ 的 $lowbit$，记位 $lbt$。如果 $x=lbt$ 说明凑到了 $2^k$；如果 $x\not= lbt$ 我们就找到 $a_{2\times lbt}=2\times lbt$ (显然 $2\times lbt < n$ ) 并操作一次 $add(2\times lbt,n)$，可以使得 $x+=lbt$。

这样我们就使得 $x$ 凑到了 $2^k$，我们要将 $x$ 变为 $1$，并把之前所有的影响消除。每次检查一下在之前操作内是否有操作过 $a_x$。如果操作过 $a_x$ 说明目前的 $a_x=x/2$ ，操作一次 $add(n,x)$ 即可使得 $a_x$ 还原 ；如果没有操作过 $a_x$ 那就不用管它，直接操作一次 $add(n,1)$。

如此我们就在 $2\times log(n)$ 次操作内交换了 $1$ 和 $n$，可以发现，上述过程具有推广性，可以直接在 $2 \times log(n)$ 的操作次数内交换 $1$ 和任意的 $x$。那么就变成了一个经典的问题，每次可以交换 $1$ 和 $x$，使得序列复原，需要几步，把置换环建出来，先将 $1$ 所在的置换环还原，之后若遍历到一个置换环就将 $1$ 交换入其中，并将这个置换环还原，对于一个环来说，若其环长为 $c$，那么还原这个置换环只需要 $c+1$ 步，由于随机排列的置换环个数为 $sqrt(n)$ 故操作总次数为 $2\times logn \times (n+sqrt(n))$，算出来操作次数大概是 $3.5e6$ 左右，由于 $2\times log n$ 的其中一个 $log$ 可以视为树状数组的 $log$，在随机数据下常数相当小，实际上操作次数大概是 $2.5e6$ 左右。

参考代码：

#include<bits/stdc++.h>
#include"seq.h"
using namespace std;
const int N=2e5+5;
int pos[N],realpos[N];
int a[N],b[N];
int vis[N];
int lowbit(int x){
    return x&(-x);
}
int cnt=0;
void swp(int key){//跟1交换 
    int posk=pos[key],pos1=pos[1];
    while(key!=lowbit(key)){
        int now=lowbit(key)*2;
        add(pos[now],posk);
        cnt++;
        vis[now]=1;
        key+=now/2;
    }
    while(key>1){
        if(vis[key])add(posk,pos[key]),vis[key]=0;
        else add(posk,pos1);
        cnt++;
        key>>=1;
    }
    swap(a[posk],a[pos1]);
    pos[a[posk]]=posk;
    pos[a[pos1]]=pos1;
}
void solve(){
    while(1){
        int pos1=pos[1];
        if(b[pos1]==1)break;
        swp(b[pos1]);
    }
}
void SEQ(int n,int M){
    for(int i=1;i<=n;i++)a[i]=i,pos[i]=i,b[i]=Get(i);
    answer(1);
    solve();
    for(int i=1;i<=n;i++)if(a[i]!=b[i]){
        swp(a[i]);
        solve();
    }
    assert(cnt<=2.5e6);
}