一遍预处理跑完所有情况，O(1)回答就好。状态记录我用的康拓和逆康拓。
#include<bits/stdc++.h>
using namespace std; int d[];
int fac[];
int u[]; int cantor()
{
int re = ;
for(int i = ; i < ; i++){
int inv = ;
for(int j = i; ++j < ; ){
if(u[i]>u[j]) inv++;
}
re += fac[-i]*inv;
}
return re;
} void invCantor(int x)
{
bool vis[] = {};
for(int i = ; i < ; i++){
int w = x/fac[-i];
x %= fac[-i];
int j = ;
for( ; j < ; j++){
if(!vis[j]){
if(!w) break;
w--;
}
}
u[i] = j; vis[j] = true;
}
} int cur;
queue<int> q; inline void updata(int p0,int p1)
{
swap(u[p0],u[p1]);
int s = cantor();
if(!d[s]){
d[s] = d[cur]+;
q.push(s);
}
swap(u[p0],u[p1]);
} void bfs()
{
d[] = ;
q.push();
while(q.size()){
invCantor(cur = q.front()); q.pop();
int p;
for(int i = ; i < ; i++)
if(!u[i]){ p = i; break; }
int r = p%;
if(r) {
updata(p-,p);
}
if(r<){
updata(p+,p);
}
updata(p,p+(p>?-:));
}
} void preDeal()
{
fac[] = ;
for(int i = ; i < ; i++){
fac[i] = fac[i-]*i;
}
bfs();
} int read()
{
if(scanf("%d",u)<) return -;
for(int i = ; i < ; i++) scanf("%d",u+i);
return cantor();
} //#define LOCAL
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
preDeal();
int s;
while( ~(s = read()) ){
printf("%d\n",d[s]-);
}
return ;
}