Сортування зсувами#13066

Сортування зсувами

2 секунди

256 мегабайтів

Задано масив $a$ , що складається з $n$ елементів $a_{1}, a_{2}, ..., a_{n}$ a_1,a_2,...,a_n.

Ви можете декілька разів виконати наступну операцію.

Виберіть індекс $i$
нехай $k$ — номер найстаршого увімкненого біта в $a_{i}$ a_i до застосування до нього будь-яких операцій
циклічно зсуньте перші $k + 1$ k+1 бітів числа $a_{i}$ a_i вліво на $1$ .

Наприклад, якщо ви виберете для зсуву $x = 4$ x=4, ви можете отримати наступне важливо!ДП з оптимізацією префіксними мінімумами за станами 18-бітових циклічних зсувів.

(100)_{2} \to (001)_{2} \to (010)_{2} \to (100)_{2} \to ...

(100)_2 \rightarrow (001)_2 \rightarrow (010)_2 \rightarrow (100)_2 \rightarrow ...

Знайдіть мінімальну кількість операцій, необхідну для сортування масиву $a$ , або виведіть $- 1$ , якщо це неможливо.

Вхідні дані

Перший рядок кожного тесту містить одне ціле число $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить одне ціле число $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) — довжину масиву $a$ .

Другий рядок кожного тестового випадку містить $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n}$ a_1 , a_2 , ... , a_n ( $1 \leq a_{i} \leq 2 \cdot 1 0^{5}$ 1 \le a_i \le 2\cdot 10 ^ 5) — масив $a$ .

Гарантується, що сума $n$ за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — мінімальну кількість операцій, необхідну для сортування масиву $a$ .

Приклади

Приклад 1

Примітка

У першому тестовому випадку ви можете вибрати $i = 2$ i = 2 та виконати операцію, щоб отримати масив $[1, 1, 3]$ [1 , 1 , 3].

Оцінювання

Підзадача $1$ ( $10$ балів): $\sum n \leq 5$ \sum n \le 5
Підзадача $2$ ( $20$ балів): $a_{i} = 2^{x} - 1$ a_i = 2^x - 1 для всіх $i$ ( $1 \leq i \leq n$ 1 \le i \le n).
Підзадача $3$ ( $20$ балів): $a_{i} \leq 3$ a_i \le 3 для всіх $i$ ( $1 \leq i \leq n$ 1 \le i \le n).
Підзадача $4$ ( $150$ балів): Без додаткових обмежень.