Masha and a Beautiful Tree
Contest: Codeforces Round 826 (Div. 3)
Difficulty rating: 1300
Tags: dfs and similar, divide and conquer, graphs, sortings, trees

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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):

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.

Example input:
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

Example output:
4
-1
0
-1

Editorial:
Let some vertex be responsible for a segment of leaves $$$[l..r]$$$. Then her left son is responsible for the segment $$$[l..\frac{l+r-1}{2}]$$$, and the right for the segment $$$[\frac{l+r+1}{2}..r]$$$. Note that if we do not apply the operation to this vertex, then it will not be possible to move some element from the right son's segment to the left son's segment. It remains to understand when we need to apply the operation to the vertex. Let the maximum on the segment $$$[l..r]$$$ be $$$max$$$, the minimum on the same segment is $$$min$$$. Then if $$$min$$$ lies in the right son, and $$$max$$$ in the left, then we should obviously apply the operation, for the reason described above. In the case when $$$min$$$ lies in the left son, and $$$max$$$ in the right, the application of the operation will definitely not allow you to get a solution. Let's continue to act in a similar way recursively from the children of the current vertex. At the end, we should check whether we have received a sorted permutation. The above solution works for $$$O(nm)$$$, since there are $$$n$$$ levels in the tree and at each level, vertexes are responsible for $$$m$$$ sheets in total. You can optimize this solution to $$$O(m)$$$ if you pre-calculate the maximum and minimum for each vertex.