F. Vessels, Heights and Two Versions (Hard Version)

题目描述

本题是困难版本。两个版本的区别在于本题中 $n$ 和测试点数量的限制更大。只有当你通过了所有版本的题目后才能对他人进行 hack。

有 $n$ 个无限高的连通容器排成一个圆环。每个容器的底面积为 $1$ cm$^2$，在第 $i$ 个容器与第 $(i \bmod n) + 1$ 个容器之间存在一个体积可忽略的连接口，其高度为 $h_i$ cm。对于每个容器 $i$，求在保证第 $i$ 个容器保持为空的前提下，这些容器中最多能装入多少总体积的水（单位 cm$^3$）。

形式化地，给定一个数组 $h_1, h_2, \ldots, h_n$。一个循环的非负整数数组 $w_1, w_2, \ldots, w_n$ 被称为「合法的」，当且仅当满足以下条件：

• 对于每个 $i$（$1 \le i \le n$），如果 $\max(w_i, w_{i \bmod n + 1}) \gt h_i$，则必有 $w_i = w_{i \bmod n + 1}$。换言之，如果数组 $w$ 中两个相邻元素的最大值超过了数组 $h$ 中对应的元素，那么这两个相邻元素必须相等。

对于每个 $i$（$1 \le i \le n$），在所有满足 $w_i = 0$ 的合法数组 $w_1, w_2, \ldots, w_n$ 中，输出可能的最大和 $w_1 + w_2 + \ldots + w_n$。

输入格式

每个测试包含多个测试点。第一行包含测试点数量 $t$（$1 \le t \le 10^4$）。随后是每个测试点的描述。

每个测试点的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）— 容器的数量。

每个测试点的第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$1 \le h_i \le 10^9$）— 容器之间隔板的高度。

保证所有测试点的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试点，输出 $n$ 个整数 — 第 $l$ 个整数表示在保持第 $l$ 个容器为空的前提下，容器中最多能装入的总体积（cm$^3$）。

4
4
1 2 3 4
5
5 3 1 5 2
6
3 4 2 6 1 5
7
1 2 1 4 2 3 5

6 6 7 9
17 16 14 14 17
21 21 20 20 21 21
17 17 17 17 21 21 22

提示

考虑第一个测试点。

• 为保持容器 $1$ 为空，一个合法数组是 $w = [0, 1, 2, 3]$，总水量为 $6$ cm$^3$。
• 为保持容器 $2$ 为空，一个合法数组是 $w = [1, 0, 2, 3]$，总水量为 $6$ cm$^3$。
• 为保持容器 $3$ 为空，一个合法数组是 $w = [2, 2, 0, 3]$，总水量为 $7$ cm$^3$。
• 为保持容器 $4$ 为空，一个合法数组是 $w = [3, 3, 3, 0]$，总水量为 $9$ cm$^3$。

例如，数组 $w = [2, 2, 0, 4]$ 不合法，因为 $\max(w_3, w_4) \gt h_3$，因此必须满足 $w_3 = w_4$。

可以证明，上述每个数组在所有可行方案中具有最大可能的总和。