题目描述

这是该问题的简单版本。两个版本之间的区别在于，在这个版本中，$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$ 被称为好的，如果满足以下条件：

• 对于从 $1$ 到 $n$ 的每个 $i$，如果 $\max(w_i, w_{i \bmod n + 1}) \gt h_i$，则 $w_i = w_{i \bmod n + 1}$。换句话说，如果数组 $w$ 的两个相邻元素的最大值超过数组 $h$ 的对应元素，则这两个相邻元素必须相等。

对于从 $1$ 到 $n$ 的每个 $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, \ldots, h_n$ ($1 \le h_i \le 10^9$) — 容器之间隔板的高度。

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

输出格式

对于每个测试用例，输出 $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$。

可以证明上述每个数组在所有合适选项中具有最大可能的和。