CF2234C.Vessels, Heights and Two Versions (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, constraints on $n$ and on the number of test cases are smaller. You can hack only if you solved all versions of this problem.

There are $n$ communicating vessels of infinite height arranged in a circle. The base area of each vessel is $1$ cm$^2$, and between the $i$-th vessel and the $(i \bmod n) + 1$-th vessel there is a connection of negligible volume at height $h_i$ cm. For each vessel $i$, find the maximum total volume of water in cm$^3$ that can be placed in these vessels under the condition that the $i$-th vessel remains empty.

Formally, you are given an array $h_1, h_2, \ldots, h_n$. A cyclic array of non-negative integers $w_1, w_2, \ldots, w_n$ is called good if the following holds:

• For every $i$ from $1$ to $n$, if $\max(w_i, w_{i \bmod n + 1}) \gt h_i$, then $w_i = w_{i \bmod n + 1}$. In other words, if the maximum of two neighboring elements of the array $w$ exceeds the corresponding element of the array $h$, then these two neighboring elements of the array $w$ must be equal.

For each $i$ from $1$ to $n$, output the maximum possible sum $w_1 + w_2 + \ldots + w_n$ among all good arrays $w_1, w_2, \ldots, w_n$, under the condition that $w_i = 0$.

这是该问题的简单版本。两个版本的区别在于，本版本中对 $n$ 和测试用例数量的限制更小。只有当你解决了该问题的所有版本后，才可进行 Hack。

有 $n$ 个无限高的连通容器，呈环形排列。每个容器的底面积均为 $1\ \text{cm}^2$，在第 $i$ 个容器与第 $(i \bmod n) + 1$ 个容器之间，于高度 $h_i\ \text{cm}$ 处存在一个体积可忽略的连通管。对于每个容器 $i$，求在保证第 $i$ 个容器为空的前提下，这些容器中所能容纳的水的最大总体积（单位：$\text{cm}^3$）。

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

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

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

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($3 \le n \le 3000$) — the number of vessels.

The second line of each test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — the heights of the partitions between the vessels.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 3000$）—— 表示容器的数量。

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

保证所有测试用例的 $n$ 之和不超过 $3000$。

For each test case, output $n$ integers — the $l$-th integer means the maximum total volume of water in cm$^3$ in the vessels under the condition that the $l$-th vessel remains empty.

对于每个测试用例，输出 $n$ 个整数——其中第 $l$ 个整数表示在第 $l$ 个容器保持为空的条件下，所有容器中水的总体积（单位：cm$^3$）的最大值。

Consider the first test case.

• To keep vessel $1$ empty, one good array is $w = [0, 1, 2, 3]$, with a total of $6$ cm$^3$ of water.
• To keep vessel $2$ empty, one good array is $w = [1, 0, 2, 3]$, with a total of $6$ cm$^3$ of water.
• To keep vessel $3$ empty, one good array is $w = [2, 2, 0, 3]$, with a total of $7$ cm$^3$ of water.
• To keep vessel $4$ empty, one good array is $w = [3, 3, 3, 0]$, with a total of $9$ cm$^3$ of water.

For example, the array $w = [2, 2, 0, 4]$ is not good, because $\max(w_3, w_4) \gt h_3$, and therefore $w_3 = w_4$ must hold.

It can be shown that each of the arrays above has the maximum possible sum among all suitable options.

考虑第一个测试用例。

• 为使容器 $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$。

可以证明，上述每个数组在其各自约束下的所有可行选项中，均具有最大的可能和。