Shifting Sort#13066
You are given an array consisting of elements a_1,a_2,...,a_n.
You can do the following operation several times.
Choose an index
let be the highest turned on bit in a_i before applying any operations on it
cycle shift the first k+1 bits in a_i to the left by .
For example, if you choose x=4 to shift , you can get the following important!Prefix-minimum optimized DP over 18-bit cyclic shift states.
Find the minimum number of operations required to sort the array or print if it's impossible.
The first line of each test case contains a single integer (1 \le t \le 10^4) — the number of test cases.
The first line of each test case contains a single integer (1 \le n \le 2 \cdot 10^5) — the length of array .
The second line of each test case contains integers a_1 , a_2 , ... , a_n (1 \le a_i \le 2\cdot 10 ^ 5) — the array .
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
For each test case, print a single integer , the minimum number of operations required to sort the array .
Example 1
In the first test case , you can choose i = 2 and perform an operation to obtain the array [1 , 1 , 3].
Subtask ( points): \sum n \le 5
Subtask ( points): a_i = 2^x - 1 for all (1 \le i \le n).
Subtask ( points): a_i \le 3 for all (1 \le i \le n).
Subtask ( points): No additional constraints.