Masha and a Beautiful Tree

题意翻译

## 题目描述 Masha 在森林里散步时发现了一棵深度为 $n$ 的满二叉树，它有 $m = 2^n$ 个叶子结点，每个叶子节点上都有一个正整数 $p_i$。 Masha 希望交换一些子树之后可以使从左往右数的第 $i$ 个叶子结点上的正整数为 $i$（因为她觉得这样的一棵满二叉树很漂亮）。你需要帮她找到最少需要交换的次数。 ## 输入格式 第一行，一个正整数 $t(1 \leq t \leq 10^4)$，表示数据组数。 每组输入由两行组成： 第一行是一个正整数 $m(1 \leq m \leq 262144)$，表示树的叶子结点的个数。 第二行，$m$ 个正整数，表示每个叶子节点上的正整数。 数据保证 $\sum m \leq 3 \times 10^5$，且 $m$ 一定为 $2$ 的整数幂。 ## 输出格式 对于每一组数据，输出一个正整数，表示最小的交换次数，或者输出一个 $-1$——如果无论怎么交换都不能使从左往右数的第 $i$ 个叶子结点上的正整数为 $i$ 。 （Translated by @[owo_ImposterAnYu_owo](https://www.luogu.com.cn/user/510555)）

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

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

说明

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.

**题目大意：**
玛莎在森林里发现了一棵深度为 $ n $ 的满二叉树，它有 $ m = 2^n $ 个叶子节点，每个叶子节点上都有一个正整数 $ p_i $。玛莎希望通过交换一些子树，使得从左往右数的第 $ i $ 个叶子节点上的正整数为 $ i $。需要帮助她找到最少需要交换的次数。

**输入格式：**
第一行，一个正整数 $ t(1 \leq t \leq 10^4) $，表示数据组数。
每组输入由两行组成：
第一行是一个正整数 $ m(1 \leq m \leq 262144) $，表示树的叶子节点的个数，且 $ m $ 一定为 $ 2 $ 的整数幂。
第二行，$ m $ 个正整数，表示每个叶子节点上的正整数。

**输出格式：**
对于每一组数据，输出一个正整数，表示最小的交换次数，或者输出一个 $-1$ —— 如果无论怎么交换都不能使从左往右数的第 $ i $ 个叶子节点上的正整数为 $ i $。**题目大意：** 玛莎在森林里发现了一棵深度为 $ n $ 的满二叉树，它有 $ m = 2^n $ 个叶子节点，每个叶子节点上都有一个正整数 $ p_i $。玛莎希望通过交换一些子树，使得从左往右数的第 $ i $ 个叶子节点上的正整数为 $ i $。需要帮助她找到最少需要交换的次数。 **输入格式：** 第一行，一个正整数 $ t(1 \leq t \leq 10^4) $，表示数据组数。 每组输入由两行组成： 第一行是一个正整数 $ m(1 \leq m \leq 262144) $，表示树的叶子节点的个数，且 $ m $ 一定为 $ 2 $ 的整数幂。 第二行，$ m $ 个正整数，表示每个叶子节点上的正整数。 **输出格式：** 对于每一组数据，输出一个正整数，表示最小的交换次数，或者输出一个 $-1$ —— 如果无论怎么交换都不能使从左往右数的第 $ i $ 个叶子节点上的正整数为 $ i $。