A16697. Inverse Minimum Partition (Hard Version)

这是该问题的困难版本。不同版本的区别在于，本版本要求你计算 $a$ 的所有连续子序列 $b$ 的 $f(b)$ 之和。只有在你解决了所有版本后，才能进行 Hack。

对于一段长度为 $k$ 的正整数序列 $b$，其“代价”定义如下$^*$：

$$ \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$ 分割后的最小总代价。

给定一个长度为 $n$ 的正整数序列 $a$，你需要计算：

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

$^*$ 给定一个实数 $x$，$\lceil x\rceil$ 定义为不小于 $x$ 的最小整数。例如，$\lceil 3.14\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$。

对于每个测试用例，输出一行答案。

对于第一个测试用例，所有 $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$。