Вам дан массив целых чисел \(a_1, a_2, \ldots, a_n\). Вам нужно сделать его неубывающим за наименьшее количество операций. За одну операцию вы делаете следующее:
- Выберите индекс \(1 \leq i \leq n\),
- Сделайте \(a_i = a_i \cdot 2\).
Массив \(b_1, b_2, \ldots, b_n\) является неубывающим, если \(b_i \leq b_{i+1}\) для всех \(1 \leq i < n\).
Выходные данные
Для каждого набора входных данных выведите наименьшее количество операций, которое нужно сделать, чтобы массив стал неубывающим.
Примечание
В первом наборе входных данных операции не нужно делать.
Во втором наборе входных данных нужно выбрать \(i = 2\), после чего массив будет равен \([2, 2]\).
В третьем наборе входных данных можно применить следующие операции:
- Выбрать \(i = 3\), после чего массив будет равен \([3, 2, 2]\),
- Выбрать \(i = 3\), после чего массив будет равен \([3, 2, 4]\),
- Выбрать \(i = 2\), после чего массив будет равен \([3, 4, 4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
1
1
2
2 1
3
3 2 1
4
7 1 5 3
5
11 2 15 7 10
6
1 8 2 16 8 16
2
624323799 708290323
12
2 1 1 3 3 11 12 22 45 777 777 1500
12
12 11 10 9 8 7 6 5 4 3 2 1
|
0
1
3
6
10
3
0
2
66
|