这是问题的困难版本。版本之间的区别在于,在该版本中,$$$t \le 10^4$$$、$$$n \le 5 \cdot 10^5$$$ 且$$$n$$$ 之和不超过$$$5 \cdot 10^5$$$。只有解决了该问题的所有版本,您才能破解。
对于长度为 $$$k$$$ 的非空序列 $$$c$$$,定义 $$$f(c)$$$ 如下:
- 海龟和小猪正在按顺序玩游戏。它们被赋予序列 $$$c_1, c_2, \ldots, c_k$$$,并且 Turtle 先行。海龟和小猪轮流交替(因此,海龟进行第一轮,小猪进行第二轮,海龟进行第三轮,依此类推)。
- 游戏进行如下:
- 令序列的当前长度为$$$m$$$。如果$$$m = 1$$$,游戏结束。
- 如果游戏没有结束,轮到 Turtle 了,那么 Turtle 必须选择一个整数 $$$i$$$,使得 $$$1 \le i \le m - 1$$$,将 $$$c_i$$$ 设置为 $$$\min(c_i, c_{i + 1})$$$,并删除 $$$c_{i + 1}$$$。
- 如果游戏没有结束,轮到 Piggy 了,那么 Piggy 必须选择一个整数 $$$i$$$,使得 $$$1 \le i \le m - 1$$$,将 $$$c_i$$$ 设置为 $$$\max(c_i, c_{i + 1})$$$,并删除 $$$c_{i + 1}$$$。
- 乌龟想要 最大化 最后$$$c_1$$$的值,而Piggy想要 最小化 最后$$$c_1$$$的值。
- 如果双方都发挥最佳,$$$f(c)$$$ 就是最终 $$$c_1$$$ 的值。
对于长度为 $$$n$$$$$$^{\text{∗}}$$$ 的排列 $$$p$$$,Turtle 定义 美女 的排列为 $$$\sum\limits_{i = 1}^n \sum\limits_{j = i}^n f([p_i, p_{i + 1}, \ldots, p_j])$$$ (即 $$$f(c)$$$ 的总和,其中 $$$c$$$ 是非空$$$p$$$ 的子段$$$^{\text{†}}$$$)。
Piggy 给 Turtle 一个长度为 $$$n$$$ 的排列 $$$a$$$,其中缺少一些元素并用 $$$0$$$ 表示。
Turtle 要求您确定长度 $$$n$$$ 的排列 $$$b$$$,使得:
- $$$b$$$ 可以通过填充 $$$a$$$ 的缺失元素来形成(即,对于所有 $$$1 \le i \le n$$$,如果 $$$a_i \ne 0$$$,则 $$$b_i = a_i$$$)。
- 排列 $$$b$$$ 的美妙之处是 最大化.
为了方便,你只需要找到这种排列$$$b$$$的最大美感即可。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^{\text{†}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子段,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$)。保证 $$$a$$$ 中不是 $$$0$$$ 的元素是不同的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 排列 $$$b$$$ 的最大美感。
示例
输入复制
821 030 0 030 1 053 2 4 5 170 3 2 5 0 0 0101 2 6 5 8 9 0 0 0 050 4 1 0 050 1 5 2 3
输出复制
4 12 11 44 110 300 45 40
注意
在第一个测试用例中,最美丽的排列 $$$b$$$ 是 $$$[1, 2]$$$。 $$$[1, 2]$$$ 的美妙之处在于 $$$4$$$,因为 $$$f([1]) + f([2]) + f([1, 2]) = 1 + 2 + 1 = 4$$$。如果$$$c = [1, 2]$$$,则$$$f(c) = 1$$$,因为Turtle只能选择$$$i = 1$$$,并且他会将$$$c_1$$$设置为$$$\min(c_1, c_2) = 1$$$。
在第二个测试用例中,最美丽的排列 $$$b$$$ 之一是 $$$[3, 2, 1]$$$。 $$$[3, 2, 1]$$$ 的美妙之处在于 $$$12$$$,因为 $$$f([3]) + f([2]) + f([1]) + f([3, 2]) + f([2, 1]) + f([3, 2, 1]) = 3 + 2 + 1 + 2 + 1 + 3 = 12$$$。
在第三个测试用例中,最美丽的排列 $$$b$$$ 之一是 $$$[2, 1, 3]$$$。
在第四个测试用例中,如果 $$$c = [3, 2, 4, 5, 1]$$$,则 $$$f(c) = 3$$$。一种可能的博弈过程如下:
- 海龟可以选择 $$$i = 3$$$。然后他将 $$$c_3$$$ 设置为 $$$\min(c_3, c_4) = 4$$$ 并删除 $$$c_4$$$。序列 $$$c$$$ 将变为 $$$[3, 2, 4, 1]$$$。
- 小猪可以选择$$$i = 1$$$。然后他将 $$$c_1$$$ 设置为 $$$\max(c_1, c_2) = 3$$$ 并删除 $$$c_2$$$。序列 $$$c$$$ 将变为 $$$[3, 4, 1]$$$。
- 海龟可以选择 $$$i = 2$$$。然后他将 $$$c_2$$$ 设置为 $$$\min(c_2, c_3) = 1$$$ 并删除 $$$c_3$$$。序列 $$$c$$$ 将变为 $$$[3, 1]$$$。
- 小猪可以选择$$$i = 1$$$。然后他将 $$$c_1$$$ 设置为 $$$\max(c_1, c_2) = 3$$$ 并删除 $$$c_2$$$。序列 $$$c$$$ 将变为 $$$[3]$$$。
- 序列的长度变为$$$1$$$,因此游戏将结束。 $$$c_1$$$ 的值最终将是 $$$3$$$。
在第五个测试用例中,最美丽的排列 $$$b$$$ 之一是 $$$[1, 3, 2, 5, 6, 4, 7]$$$。