#include<cstdio>#include<algorithm>using namespace std;typedef unsigned long long ll;const int N=12,M=363000;int n,i,j,k,a[N],len[N],S,x,z,v[M],g[M],h,t,q[M],ans;ll f[N][M];inline ll encode(){  ll t=0;  for(int i=0;i<n;i++)t=t<<4|a[i];  return t;}inline int getid(ll x){  int l=0,r=len[n]-1;  while(l<=r){    int mid=(l+r)>>1;    if(f[n][mid]==x)return mid;    if(f[n][mid]<x)l=mid+1;else r=mid-1;  }}inline void ext(int x){  if(~v[x])return;  v[q[++t]=x]=z;}int main(){  for(n=2;n<=9;n++){    for(i=0;i<n;i++)a[i]=i;    do{f[n][len[n]++]=encode();}while(next_permutation(a,a+n));    sort(f[n],f[n]+len[n]);  }  while(~scanf("%d",&n)){    if(!n)return 0;    for(i=0;i<n;i++)scanf("%d",&a[i]),a[i]--;    if(n==1){puts("0");continue;}    S=getid(encode());    h=1,t=0;    for(i=0;i<len[n];i++)v[i]=-1;    z=0;    ext(S);    while(h<=t){      z=v[x=q[h++]]+1;      if(z>2)continue;      ll O=f[n][x];      for(i=1;i<n;i++)for(j=i;j<n;j++){        ll U=(1ULL<<((j-i+2)*4))-1,F=O;        int L=(j-i+1)*4;        for(k=4*(i-1);k>=0;k-=4){          ll A=(F>>k)&U;          F^=(A^((A>>4)|(A&15)<<L))<<k;          ext(getid(F));        }      }    }    for(i=0;i<len[n];i++)g[i]=v[i],v[i]=-1;    h=1,t=z=0;    ext(0);    while(h<=t){      z=v[x=q[h++]]+1;      if(z>2)continue;      ll O=f[n][x];      for(i=1;i<n;i++)for(j=i;j<n;j++){        ll U=(1ULL<<((j-i+2)*4))-1,F=O;        int L=(j-i+1)*4;        for(k=4*(i-1);k>=0;k-=4){          ll A=(F>>k)&U;          F^=(A^((A>>4)|(A&15)<<L))<<k;          ext(getid(F));        }      }    }    for(ans=5,i=0;i<len[n];i++)if(~v[i]&&~g[i])ans=min(ans,v[i]+g[i]);    printf("%d\n",ans);  }  return 0;}