CF2234C Vessels, Heights and Two Versions (Easy Version)

这是该问题的简单版本。不同版本之间的区别在于本版本中 $n$ 和测试用例数量的约束更小。只有在你解决所有版本的本题后才能进行 hack。 有 $n$ 个无限高的连通容器，按环形排列。每个容器底面积为 $1\,\mathrm{cm}^2$，并且第 $i$ 个容器与第 $(i \bmod n) + 1$ 个容器之间，在高度为 $h_i$ $\mathrm{cm}$ 处有一个体积可忽略不计的连通管。对于每个容器 $i$，请找出在第 $i$ 个容器保持为空的前提下，能放入这些容器中的水的最大总体积（单位为 $\mathrm{cm}^3$）。 形式化地，给定数组 $h_1, h_2, \ldots, h_n$。称数组 $w_1, w_2, \ldots, w_n$（是一个循环数组，元素非负整数）是“好”的，若对每个 $i$ 从 $1$ 到 $n$，若 $\max(w_i, w_{i \bmod n + 1}) > h_i$，则 $w_i = w_{i \bmod n + 1}$。换句话说，如果数组 $w$ 相邻两元素的最大值超出了对应 $h$ 中的分隔高度，则这两个相邻元素的数值必须相等。 对于每个 $i$，请输出在 $w_i = 0$ 的条件下，所有“好”数组 $w_1, w_2, \ldots, w_n$ 中 $w_1 + w_2 + \ldots + w_n$ 的最大值。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 1000$）。接下来依次给出每个测试用例的描述。 每个测试用例第一行包含一个整数 $n$（$3 \le n \le 3000$）——容器的个数。 第二行包含 $n$ 个整数 $h_1, h_2, ..., h_n$（$1 \le h_i \le 10^9$）——容器之间隔板的高度。 保证所有测试用例中 $n$ 的总和不超过 $3000$。

对于每个测试用例，输出 $n$ 个整数，第 $l$ 个数表示在第 $l$ 个容器为空时，这些容器可容纳的水的最大总体积（$\mathrm{cm}^3$）。

考虑第一个测试用例。 - 若保持第 $1$ 个容器为空，可以选用 $w = [0, 1, 2, 3]$，总共 $6\,\mathrm{cm}^3$ 的水。 - 若保持第 $2$ 个容器为空，可以选用 $w = [1, 0, 2, 3]$，总共 $6\,\mathrm{cm}^3$ 的水。 - 若保持第 $3$ 个容器为空，可以选用 $w = [2, 2, 0, 3]$，总共 $7\,\mathrm{cm}^3$ 的水。 - 若保持第 $4$ 个容器为空，可以选用 $w = [3, 3, 3, 0]$，总共 $9\,\mathrm{cm}^3$ 的水。 例如，$w = [2, 2, 0, 4]$ 不是“好”的数组，因为 $\max(w_3, w_4) > h_3$，所以要求 $w_3 = w_4$ 才符合条件。 可以证明，上述每组数组在符合条件的所有方案中都达到最大总和。 由 ChatGPT 5 翻译