CF2159D2.Inverse Minimum Partition (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, you are asked to find the sum of $f(b)$ over all contiguous subsequences $b$ of $a$. You can hack only if you solved all versions of this problem.

For some sequence $b$ of $k$ positive integers, the cost of the sequence is defined as follows$^{\text{∗}}$:

$$\\mathtt{cost}(b)=\\left\\lceil{\\frac{b\_k}{\\min(b\_1,b\_2,\\ldots,b\_k)}}\\right\\rceil$$

Assume that you partition a sequence $c$ into one or more sequences, so that the sequences become $c$ when concatenated. For example, when the sequence $c$ is $[3,1,4,1,5]$, a few valid ways to partition the sequence are $[[3,1],[4,1,5]]$, $[[3],[1,4,1],[5]]$, $[[3,1,4,1,5]]$. On the other hand, $[[3,1],[1,5]]$ and $[[3,4,1],[1,5]]$ are not valid ways to partition the sequence.

For a partition of a sequence $c$ of positive integers, the total cost of the partition is defined as the sum of the costs of each sequence in the partition. Then, let us define $f(c)$ as the minimum total cost to partition the sequence $c$.

Given a sequence $a$ of $n$ positive integers, you must compute the following:

\\sum\_{l=1}^{n} {\\sum\_{r=l}^{n} f(\[a\_l,a\_{l+1},\\ldots,a\_r\])}

$^{\text{∗}}$Given a real value $x$, $\left\lceil{x}\right\rceil$ is defined as the smallest integer no less than $x$. For example, the value of $\left\lceil{3.14}\right\rceil$ is $4$.

这是该问题的困难版本。两个版本的区别在于：在本版本中，你需要计算 $f(b)$ 在数组 $a$ 的所有连续子序列 $b$ 上的总和。仅当你解决了该问题的所有版本时，你才可进行 Hack。

对于某个由 $k$ 个正整数组成的序列 $b$，其代价定义如下$^{\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$ 所能得到的最小总代价。

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

$$\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$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$).

The second line of each test case contains $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^{18}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $4 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output the answer to the problem on a separate line.

对于每个测试用例，在单独的一行上输出该问题的答案。

For the first test case, the following are all contiguous subsequences of $a$ and their corresponding values:

• $[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$.

Therefore, the answer for the first test case is $1+1+2+1+2+1+2+1+2+1+1+2+1+2+1=21$.

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