有一个题目是给定一个长度为 $n$ 的排列 $a[1,\dots,n]$，可以交换 $a[i]\neq i,a[i+1]\neq i+1$ 的 $a[i],a[i+1]$，要求构造操作序列使得 $a[i]=i$，操作序列长度最严格的约束是长度不超过 $\frac{n(n-1)}{2}$。

使用两颗星神力判掉无解在这里不讨论，按照先把 $a[i]>i$ 移到左边然后对于 $a[i]>i,a[i]<i$ 的部分做冒泡，再整个一起做冒泡，这样构造可以保证次数嘛？如果可以保证是为什么。打表的结论是应该可以。

up(i,1,n) dn(j,i,2) if(a[j]>j&&a[j-1]<j-1) swap(a[j],a[j-1]);
up(i,1,n) dn(j,i,2) if(j>a[j]&&j-1>a[j-1]&&a[j]<a[j-1]) swap(a[j],a[j-1]);
up(i,1,n) dn(j,i,2) if(j<a[j]&&j-1<a[j-1]&&a[j]<a[j-1]) swap(a[j],a[j-1]);
up(i,1,n) dn(j,i,2) if(j!=a[j]&&j-1!=a[j-1]&&a[j]<a[j-1]) swap(a[j],a[j-1]);