CF2234F Vessels, Heights and Two Versions (Hard Version)

本题为困难版本，两个版本的区别在于本版本对 $n$ 和测试用例数量的限制更高。只有完成本题所有版本才能提交 hack。 有 $n$ 个无限高的连通容器围成一个圆环。每个容器底面积为 $1\ \text{cm}^2$，第 $i$ 个容器与第 $(i \bmod n) + 1$ 个容器之间存在一条体积可忽略的连通通道，通道高度为 $h_i$ 厘米。对于每个容器 $i$，求出在**第 $i$ 个容器保持为空**的条件下，所有容器中能装入的最大总水量（单位 $\text{cm}^3$）。 形式化描述：给定数组 $h_1, h_2, \dots, h_n$。环形非负数组 $w_1, w_2, \dots, w_n$ 被称为合法数组，当且仅当满足： - 对每一个 $i \in [1,n]$，若 $\max(w_i, w_{i \bmod n + 1}) > h_i$，则必有 $w_i = w_{i \bmod n + 1}$。 通俗来说：若相邻两个容器水位的最大值超过二者之间隔板高度，则这两个容器水位必须相等。 对每个 $i \in [1,n]$，在所有满足 $w_i = 0$ 的合法数组 $w$ 中，输出总和 $w_1 + w_2 + \dots + w_n$ 的最大值。

多组测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。随后依次给出每组测试用例： 每组第一行输入整数 $n$（$3 \le n \le 2 \cdot 10^5$）——容器个数。 第二行输入 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 10^9$）——容器间隔板高度数组。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对每组测试用例输出 $n$ 个整数，第 $l$ 个数字代表强制第 $l$ 个容器为空时，容器可容纳的最大总水量。

以第一组测试用例举例： - 让 1 号容器为空：合法数组 $w = [0, 1, 2, 3]$，总水量 $6\ \text{cm}^3$。 - 让 2 号容器为空：合法数组 $w = [1, 0, 2, 3]$，总水量 $6\ \text{cm}^3$。 - 让 3 号容器为空：合法数组 $w = [2, 2, 0, 3]$，总水量 $7\ \text{cm}^3$。 - 让 4 号容器为空：合法数组 $w = [3, 3, 3, 0]$，总水量 $9\ \text{cm}^3$。 举反例：数组 $w = [2, 2, 0, 4]$ 不合法。因为 $\max(w_3, w_4) > h_3$，此时必须满足 $w_3 = w_4$，但 $0 \neq 4$。 上述每组数组都可以证明是对应限制下总和最大的合法方案。