D1. Обратно минимальное разбиение (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно только найти $$$f(a)$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Для некоторой последовательности $$$b$$$ из $$$k$$$ целых положительных чисел стоимость последовательности определяется следующим образом$$$^{\text{∗}}$$$:

$$$$$$\mathtt{cost}(b)=\left\lceil{\frac{b_k}{\min(b_1,b_2,\ldots,b_k)}}\right\rceil$$$$$$

Предположим, что вы разбиваете последовательность $$$c$$$ на одну или несколько последовательностей, так что при их конкатенации получается $$$c$$$. Например, когда последовательность $$$c$$$ равна $$$[3,1,4,1,5]$$$, несколько допустимых способов разбить последовательность: $$$[[3,1],[4,1,5]]$$$, $$$[[3],[1,4,1],[5]]$$$, $$$[[3,1,4,1,5]]$$$. С другой стороны, $$$[[3,1],[1,5]]$$$ и $$$[[3,4,1],[1,5]]$$$ не являются допустимыми способами разбить последовательность.

Для разбиения последовательности $$$c$$$ из целых положительных чисел общая стоимость разбиения определяется как сумма стоимостей каждой последовательности в разбиении. Тогда определим $$$f(c)$$$ как минимальную общую стоимость для разбиения последовательности $$$c$$$.

Дана последовательность $$$a$$$ из $$$n$$$ целых положительных чисел, вам нужно вычислить значение $$$f(a)$$$.

$$$^{\text{∗}}$$$Для действительного значения $$$x$$$, $$$\left\lceil{x}\right\rceil$$$ определяется как наименьшее целое число, не меньшее $$$x$$$. Например, значение $$$\left\lceil{3.14}\right\rceil$$$ равно $$$4$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{18}$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$4\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите на отдельной строке ответ на задачу.

Пример
Входные данные
4
5
3 1 4 1 5
10
9 2 6 5 3 5 8 9 7 9
8
1 2 3 4 5 6 7 8
2
1 1000000000000000000
Выходные данные
2
4
5
2
Примечание

Для первого набора входных данных разбиение $$$[[3,1,4,1],[5]]$$$ дает общую стоимость $$$1+1=2$$$.

Для второго набора входных данных разбиение $$$[[9,2,6,5,3],[5,8,9,7,9]]$$$ дает общую стоимость $$$2+2=4$$$.

Для третьего набора входных данных разбиение $$$[[1],[2,3,4],[5,6,7,8]]$$$ дает общую стоимость $$$1+2+2=5$$$.

Для четвертого набора входных данных разбиение $$$[[1],[1\,000\,000\,000\,000\,000\,000]]$$$ дает общую стоимость $$$1+1=2$$$.