名叫玛莎的女孩在森林里散步,发现了一棵高度为$$$n$$$的完全二叉树和长度为$$$m=2^n$$$的排列$$$p$$$。
高度为 $$$n$$$ 的完全二叉树是一棵有根树,除了叶子之外的每个顶点都恰好有两个儿子,并且从根到任何叶子的路径长度为 $$$n$$$。下图显示了$$$n=2$$$的完整二叉树。
排列是由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数组成的数组。例如,[$$$2,3,1,5,4$$$] 是一个排列,但 [$$$1,2,2$$$] 不是($$$2$$$ 出现了两次),并且 [$$$1,3,4$$$] 也不是一个排列($$$n=3$$$,但数组中有 $$$4$$$)。
让我们从左到右枚举这棵树的 $$$m$$$ 叶子。编号为 $$$i$$$ 的叶子包含值 $$$p_i$$$ ($$$1 \le i \le m$$$)。
例如,如果 $$$n = 2$$$, $$$p = [3, 1, 4, 2]$$$,树将如下所示:
如果一棵树的叶子中的值从左到右按升序排列,玛莎就会认为这棵树是美丽的。
在一次操作中,Masha 可以选择树的任何非叶顶点并交换其左右儿子(及其子树)。
例如,如果 Masha 将此操作应用于上面讨论的树的根,它将采用以下形式:
帮助玛莎了解她是否可以通过一定次数的操作使一棵树变得美丽。如果她可以,那么输出最少的操作次数才能使树变得漂亮。
输入
第一行包含单个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
在每个测试用例中,第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 262144$$$),它是 2 的幂 — 排列 $$$p$$$ 的大小。
第二行包含 $$$m$$$ 整数:$$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le m$$$) — 排列 $$$p$$$。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于单独行中的每个测试用例,打印 Masha 能够使树变得美丽的最小可能操作数,如果不可能,则打印 -1。
示例
输入 #1
4 8 6 5 7 8 4 3 1 2 4 3 1 4 2 1 1 8 7 8 4 3 1 2 6 5
输出 #1
4 -1 0 -1
注意
考虑第一个测试。
在第一个测试用例中,您可以像这样操作(当前步骤中应用操作的顶点以紫色突出显示):
在第二个测试用例中,可以证明不可能使一棵树变得美丽。
在第三个测试用例中,树已经很漂亮了。