Table of Contents

## Masha and a Beautiful Tree solution codeforces

**Masha and a Beautiful Tree solution codeforces** – The girl named Masha was walking in the forest and found a complete binary tree of height 𝑛n and a permutation 𝑝p of length 𝑚=2𝑛m=2n.

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 𝑛=2n=2.

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

Let’s enumerate 𝑚m leaves of this tree from left to right. The leaf with the number 𝑖i contains the value 𝑝𝑖pi (1≤𝑖≤𝑚1≤i≤m).

## [Solution] Masha and a Beautiful Tree solution codeforces

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

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

## [Solution] Masha and a Beautiful Tree solution codeforces

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

The first line contains single integer 𝑡t (1≤𝑡≤1041≤t≤104) — number of test cases.

In each test case, the first line contains an integer 𝑚m (1≤𝑚≤2621441≤m≤262144), which is a power of two — the size of the permutation 𝑝p.

## [Solution] Masha and a Beautiful Tree solution codeforces

The second line contains 𝑚m integers: 𝑝1,𝑝2,…,𝑝𝑚p1,p2,…,pm (1≤𝑝𝑖≤𝑚1≤pi≤m) — the permutation 𝑝p.

It is guaranteed that the sum of 𝑚m over all test cases does not exceed 3⋅1053⋅105.

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.

input

output

4 -1 0 -1

## [Solution] Masha and a Beautiful Tree solution codeforces

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.