这是问题的困难版本。版本之间的差异在于,在此版本中,要求您计算 $$$a$$$ 的所有连续子序列 $$$b$$$ 上的 $$$f(b)$$$ 之和。只有解决了该问题的所有版本,您才能破解。
对于$$$k$$$正整数的某些序列$$$b$$$,该序列的成本定义如下$$$^{\text{*}}$$$:
$$\mathtt{成本}(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$$$。
输出
对于每个测试用例,在单独的行上输出问题的答案。
示例
输入复制
453 1 4 1 5109 2 6 5 3 5 8 9 7 981 2 3 4 5 6 7 821 1000000000000000000
输出复制
21124844
注意
对于第一个测试用例,以下是 $$$a$$$ 的所有连续子序列及其对应的值:
- $$$[3] \到 [[3]]$$$: $$$f([3])=1$$$;
- $$$[3,1] \到 [[3,1]]$$$: $$$f([3,1])=1$$$;
- $$$[3,1,4] \到 [[3,1],[4]]$$$: $$$f([3,1,4])=2$$$;
- $$$[3,1,4,1] \到 [[3,1,4,1]]$$$: $$$f([3,1,4,1])=1$$$;
- $$$[3,1,4,1,5] \到 [[3,1,4,1],[5]]$$$: $$$f([3,1,4,1,5])=2$$$;
- $$$[1] \到 [[1]]$$$: $$$f([1])=1$$$;
- $$$[1,4] \到 [[1],[4]]$$$: $$$f([1,4])=2$$$;
- $$$[1,4,1] \到 [[1,4,1]]$$$: $$$f([1,4,1])=1$$$;
- $$$[1,4,1,5] \到 [[1,4,1],[5]]$$$: $$$f([1,4,1,5])=2$$$;
- $$$[4] \到 [[4]]$$$: $$$f([4])=1$$$;
- $$$[4,1] \到 [[4,1]]$$$: $$$f([4,1])=1$$$;
- $$$[4,1,5] \到 [[4,1],[5]]$$$: $$$f([4,1,5])=2$$$;
- $$$[1] \到 [[1]]$$$: $$$f([1])=1$$$;
- $$$[1,5] \到 [[1],[5]]$$$: $$$f([1,5])=2$$$;
- $$$[5] \ 到 [[5]]$$$: $$$f([5])=1$$$。
因此,第一个测试用例的答案是$$$1+1+2+1+2+1+2+1+2+1+1+2+1+2+1=21$$$。