【题目描述】
汉诺塔升级了：现在我们有?个圆盘和?个柱子，每个圆盘大小都不一样，
大的圆盘不能放在小的圆盘上面，?个柱子从左到右排成一排。每次你可以将一
个柱子上的最上面的圆盘移动到右边或者左边的柱子上 （如果移动之后是合法的
话） 。 现在告诉你初始时的状态， 你希望用最少的步数将第?大的盘子移动到第?根
柱子上，问最小步数。
【输入格式】
第一行一个正整数?，代表询问的组数。
接下来?组数据，每组数据第一行一个整数?。
接下来一行每行?个正整数，代表每个柱子上圆盘的大小。
【输出格式】
输出共?行，代表每次的答案。如果方案不存在，输出“−1” 。
【样例输入】
4
3
2 1 3
2
7 8
2
10000 1000
3
97 96 95
【样例输出】
4
0
-1
20
【样例解释】
无。
【数据范围与规定】
对于70%的数据，N的值都是相等的。
对于100%的数据，1 ≤ T ≤ 6 × 10^3 ,1 ≤ N ≤ 7。
/*
这个题改了n个小时了，最后还是看的题解……
刚开始从初始状态向目标状态找的，30分，TLE
后来又从目标状态向初始状态找，把每种情况的步数走记下来，查询就简单了，结果全TLE了，看的题解，原来是我的每个状态记得东西太多了，导致常数太大，其实只要记录每个数在哪个位置，还有每个位置的顶部是哪个数就好了。
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define M 10000000
using namespace std;
int n,top[],pos[],res[M],q[M],bit[],head,tail,w[],num[];
bool use[M];
bool cmp(int a,int b)
{
return w[a]<w[b];
}
void work(int s)
{
int x=;
int ss=s;
for(int a=;a<=;a++)
top[a]=;
while(ss)
{
x++;
pos[x]=ss%;
ss/=;
}
reverse(pos+,pos+x+);//倒置
for(int a=x;a>=;a--)
top[pos[a]]=a;
for(int a=;a<=x;a++)
if(a==top[pos[a]])
{
int p=pos[a];
if (p!=&&(a<top[p-]||!top[p-]))
{
int news=s-bit[x-a];
if(!use[news])
{
q[++tail]=news;
use[news]=true;
res[news]=res[s]+;
}
}
if(p!=x&&(a<top[p+]||!top[p+]))
{
int news=s+bit[x-a];
if(!use[news])
{
q[++tail]=news;
use[news]=true;
res[news]=res[s]+;
}
}
}
} int main()
{
//freopen("huakai.in","r",stdin);
//freopen("huakai.out","w",stdout);
head=,tail=;
int status=;
bit[]=;
for (int i=;i<=;i++)
{
bit[i]=bit[i-]*;
status=status*+i;
q[++tail]=status;
use[status]=true;
}
while(head<=tail)
{
int s=q[head++];
work(s);
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&w[i]),num[i]=i;
sort(num+,num+n+,cmp);
int s=;
for (int i=;i<=n;i++)
s=s*+num[i];
if (!use[s]) printf("-1\n");
else printf("%d\n",res[s]);
}
return ;
}