Поликарп называет массив плотным, если в любой паре двух соседних элементов больший элемент не более чем в два раза превышает меньший. Более формально, для любого \(i\) (\(1 \le i \le n-1\)) должно быть выполнено условие: \(\)\frac{\max(a[i], a[i+1])}{\min(a[i], a[i+1])} \le 2\(\)
Например, массивы \([1, 2, 3, 4, 3]\), \([1, 1, 1]\) и \([5, 10]\) — плотные. А массивы \([5, 11]\), \([1, 4, 2]\), \([6, 6, 1]\) — нет.
Вам дан массив \(a\), состоящий из \(n\) целых чисел. Какое минимальное количество чисел необходимо добавить в массив, чтобы он стал плотным? Вставлять числа можно в любое место массива. Если массив уже является плотным, то числа добавлять не надо.
Например, если \(a=[4,2,10,1]\), то ответ равен \(5\), а сам массив после вставки в него элементов может выглядеть так: \(a=[4,2,\underline{\textbf{3}},\underline{\textbf{5}},10,\underline{\textbf{6}},\underline{\textbf{4}},\underline{\textbf{2}},1]\) (есть и другие оптимальные способы построить плотный массив \(a\)).
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных можно вставить один элемент, \(a=[1,\underline{\textbf{2}},3]\).
В третьем наборе входных данных можно вставить два элемента, \(a=[6,\underline{\textbf{4}},\underline{\textbf{2}},1]\).
В четвертом наборе входных данных можно вставить один элемент, \(a=[1,\underline{\textbf{2}},4,2]\).
В пятом наборе входных данных массив \(a\) уже плотный.