Заданы \(n\) целых чисел \(a_1, a_2, \dots, a_n\). Над ними можно совершать следующую операцию:
- выбрать произвольный элемент \(a_i\) (\(1 \le i \le n\)) и поделить его на \(2\) (округляем вниз). Другими словами, можно заменить любой выбранный элемент \(a_i\) на значение \(\left \lfloor \frac{a_i}{2}\right\rfloor\) (где \(\left \lfloor x \right\rfloor\) — округление вниз вещественного числа \(x\)).
Выведите минимальное количество операций, которое необходимо совершить, чтобы последовательность чисел стала строго возрастающей (то есть, чтобы было выполнено условие \(a_1 \lt a_2 \lt \dots \lt a_n\)). Или определите, что такую последовательность получить невозможно. Обратите внимание на то, что элементы нельзя менять местами. Единственная возможная операция описана выше.
Например, пусть \(n = 3\) и задана последовательность чисел \([3, 6, 5]\). Тогда достаточно совершить над ней две операции:
- записать вместо числа \(a_2=6\) число \(\left \lfloor \frac{6}{2}\right\rfloor = 3\) и получить последовательность \([3, 3, 5]\);
- затем записать вместо числа \(a_1=3\) число \(\left \lfloor \frac{3}{2}\right\rfloor = 1\) и получить последовательность \([1, 3, 5]\).
Полученная последовательность является строго возрастающей, так как \(1 \lt 3 \lt 5\).
Выходные данные
Для каждого набора входных данных в отдельной строке выведите единственное число — минимальное количество операций, которое нужно совершить над последовательностью, чтобы она стала строго возрастающей. Если строго возрастающую последовательность невозможно получить, то выведите «-1».
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных получить строго возрастающую последовательность невозможно.
В третьем наборе входных данных последовательность уже является строго возрастающей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
3
3 6 5
4
5 3 2 1
5
1 2 3 4 5
1
1000000000
4
2 8 7 5
5
8 26 5 21 10
2
5 14
|
2
-1
0
0
4
11
0
|