Background

^_^

Description

汉诺塔升级了：现在我们有𝑁个圆盘和𝑁个柱子，每个圆盘大小都不一样，
大的圆盘不能放在小的圆盘上面，𝑁个柱子从左到右排成一排。每次你可以将一
个柱子上的最上面的圆盘移动到右边或者左边的柱子上（如果移动之后是合法的
话）。现在告诉你初始时的状态，你希望用最少的步数将第𝑖大的盘子移动到第𝑖根
柱子上，问最小步数。

Format

Input

第一行一个正整数𝑇，代表询问的组数。
接下来𝑇组数据，每组数据第一行一个整数𝑁。
接下来一行每行𝑁个正整数，代表每个柱子上圆盘的大小。

Output

输出共𝑇行，代表每次的答案。如果方案不存在，输出“−1”。

Sample 1

Input

4
3
2 1 3
2
7 8
2
10000 1000
3
97 96 95

Output

4
0
-1
20

Limitation

1s, 1024KiB for each test case.

对于70%的数据，𝑁的值都是相等的。
对于100%的数据，1 ≤ 𝑇 ≤ 6 × 103, 1 ≤ 𝑁 ≤ 7。

Source

嘉兴一中实验学校 DoubleC（供题）
原题来自：Zhong Haoxi