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

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно найти сумму $$$f(b)$$$ по всем смежным подпоследовательностям $$$b$$$ массива $$$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$$$ целых положительных чисел, вам нужно вычислить следующее значение:

$$$$$$\sum_{l=1}^{n} {\sum_{r=l}^{n} f([a_l,a_{l+1},\ldots,a_r])}$$$$$$

$$$^{\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
Выходные данные
21
124
84
4
Примечание

В первом наборе входных данных, все подмассивы $$$a$$$ и соответствующие им значения таковы:

  • $$$[3] \to [[3]]$$$: $$$f([3])=1$$$;
  • $$$[3,1] \to [[3,1]]$$$: $$$f([3,1])=1$$$;
  • $$$[3,1,4] \to [[3,1],[4]]$$$: $$$f([3,1,4])=2$$$;
  • $$$[3,1,4,1] \to [[3,1,4,1]]$$$: $$$f([3,1,4,1])=1$$$;
  • $$$[3,1,4,1,5] \to [[3,1,4,1],[5]]$$$: $$$f([3,1,4,1,5])=2$$$;
  • $$$[1] \to [[1]]$$$: $$$f([1])=1$$$;
  • $$$[1,4] \to [[1],[4]]$$$: $$$f([1,4])=2$$$;
  • $$$[1,4,1] \to [[1,4,1]]$$$: $$$f([1,4,1])=1$$$;
  • $$$[1,4,1,5] \to [[1,4,1],[5]]$$$: $$$f([1,4,1,5])=2$$$;
  • $$$[4] \to [[4]]$$$: $$$f([4])=1$$$;
  • $$$[4,1] \to [[4,1]]$$$: $$$f([4,1])=1$$$;
  • $$$[4,1,5] \to [[4,1],[5]]$$$: $$$f([4,1,5])=2$$$;
  • $$$[1] \to [[1]]$$$: $$$f([1])=1$$$;
  • $$$[1,5] \to [[1],[5]]$$$: $$$f([1,5])=2$$$;
  • $$$[5] \to [[5]]$$$: $$$f([5])=1$$$.

Поэтому ответ равняется $$$1+1+2+1+2+1+2+1+2+1+1+2+1+2+1=21$$$.