这是问题的困难版本。版本之间的差异在于,在此版本中,您必须计算所有子段的值之和。只有解决了该问题的所有版本,您才能破解。
让我们定义一个算法来生成 $$$m+k$$$ 整数序列,如下所示:
- 首先,接收 $$$x$$$ 个 $$$m$$$ 整数序列作为输入。如果$$$k=0$$$,则立即终止并返回序列$$$x$$$。
- 然后,选择任意索引 $$$1 \le i \le |x|$$$ 并插入 $$$(x_i+1)$$$ 紧接着 元素$$$x_i$$$。
- 如果 $$$x$$$ 恰好包含 $$$m+k$$$ 整数,则终止并返回序列 $$$x$$$。否则,返回第二步。
爱丽丝知道这个算法是一个古代文明为了安全地隐藏他们的秘密而使用的。 Alice想要学习他们想要隐藏的知识,但是从算法的输出推断输入并不是一件容易的事。
对于 $$$n$$$ 整数的序列 $$$b$$$,让我们将 $$$f(b)$$$ 定义为 最短 序列可以作为算法的输入给出,以生成 $$$b$$$。
给定 $$$a$$$ 的 $$$n$$$ 整数序列,请计算以下总和的值
$$\sum_{l=1}^n {\sum_{r=l}^n {f([a_l,a_{l+1},\ldots,a_r])}}$$
换句话说,你必须找到所有 $$$f(c)$$$ 的总和 子段$$$^{\text{*}}$$$ $$$c$$$ 的 $$$a$$$。
$$$^{\text{*}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子段,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。如果两个子段的集合被认为是不同的 职位 删除的元素的 不同。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$300\,000$$$。
输出
对于每个测试用例,在单独的行上输出答案。
示例
输入复制
551 2 3 4 551 3 5 7 951 2 5 6 571 2 4 5 3 7 899 8 9 2 3 4 4 5 3
输出复制
1535256078
注意
在第一个测试用例中,$$$a=[1,2,3,4,5]$$$ 的所有子段都可以从长度为 $$$1$$$ 的序列生成。
在第二个测试用例中,$$$a=[1,3,5,7,9]$$$的所有子段 不能 可以从任何比其自身更短的序列生成。