CF1741D.Masha and a Beautiful Tree

The girl named Masha was walking in the forest and found a complete binary tree of height $n$ and a permutation $p$ of length $m=2^n$.

A complete binary tree of height $n$ is a rooted tree such that every vertex except the leaves has exactly two sons, and the length of the path from the root to any of the leaves is $n$. The picture below shows the complete binary tree for $n=2$.

A permutation is an array consisting of $n$ different integers from $1$ to $n$. For example, [$2,3,1,5,4$] is a permutation, but [$1,2,2$] is not ($2$ occurs twice), and [$1,3,4$] is also not a permutation ($n=3$, but there is $4$ in the array).

Let's enumerate $m$ leaves of this tree from left to right. The leaf with the number $i$ contains the value $p_i$ ($1 \le i \le m$).

For example, if $n = 2$, $p = [3, 1, 4, 2]$, the tree will look like this:

Masha considers a tree beautiful if the values in its leaves are ordered from left to right in increasing order.

In one operation, Masha can choose any non-leaf vertex of the tree and swap its left and right sons (along with their subtrees).

For example, if Masha applies this operation to the root of the tree discussed above, it will take the following form:

Help Masha understand if she can make a tree beautiful in a certain number of operations. If she can, then output the minimum number of operations to make the tree beautiful.

名叫玛莎的女孩在森林中行走时，发现了一棵高度为 $n$ 的完全二叉树和一个长度为 $m=2^n$ 的排列 $p$。

高度为 $n$ 的完全二叉树是一棵有根树，满足：除叶子节点外，每个节点恰好有两个子节点，且从根节点到任意叶子节点的路径长度均为 $n$。下图展示了 $n=2$ 时的完全二叉树：

排列是指由 $1$ 到 $n$ 中 $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]$，则该树如下图所示：

玛莎认为一棵树是“优美的”，当且仅当其叶子节点中的数值从左到右严格递增。

在一次操作中，玛莎可以选择树中任意一个非叶子节点，并交换其左子节点与右子节点（连同各自的子树）。

例如，若玛莎对上述树的根节点执行该操作，则树将变为如下形态：

请帮助玛莎判断：她能否通过若干次操作使该树变得优美？若可以，请输出使其优美的最少操作次数。

The first line contains single integer $t$ ($1 \le t \le 10^4$) — number of test cases.

In each test case, the first line contains an integer $m$ ($1 \le m \le 262144$), which is a power of two — the size of the permutation $p$.

The second line contains $m$ integers: $p_1, p_2, \dots, p_m$ ($1 \le p_i \le m$) — the permutation $p$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例，第一行包含一个整数 $m$（$1 \le m \le 262144$），且 $m$ 是 $2$ 的幂 —— 即排列 $p$ 的长度。

第二行包含 $m$ 个整数：$p_1, p_2, \dots, p_m$（$1 \le p_i \le m$）—— 排列 $p$。

保证所有测试用例中 $m$ 的总和不超过 $3 \cdot 10^5$。

For each test case in a separate line, print the minimum possible number of operations for which Masha will be able to make the tree beautiful or -1, if this is not possible.

对于每个测试用例，在单独的一行中输出玛莎使树变得“美丽”所需的最少操作次数；如果无法实现，则输出 $-1$。

Consider the first test.

In the first test case, you can act like this (the vertex to which the operation is applied at the current step is highlighted in purple):

It can be shown that it is impossible to make a tree beautiful in fewer operations.

In the second test case, it can be shown that it is impossible to make a tree beautiful.

In the third test case, the tree is already beautiful.

考虑第一个测试用例。

在第一个测试用例中，你可以按如下方式操作（当前步骤中执行操作的顶点以紫色高亮显示）：

可以证明：无法用少于上述次数的操作将该树变为“优美树”。

在第二个测试用例中，可以证明：无法将该树变为“优美树”。

在第三个测试用例中，该树本身已是“优美树”。