T373741 2023省熟中集训#8 D 序列

给一个序列 $a_1,a_2,\cdots,a_n$ ，你每次可以选择一个 $i(2\le i\le n-1)$ ，然后将 $a_{i-1},a_i,a_{i+1}$ 全都变成 $\max(a_{i-1},a_i,a_{i+1})$ 。 你可以进行 $k$ 次这样的操作，目标是最大化 $\sum^n_{i=1}a_i$ ，求最后的答案。 你需要对 $k=1,2,\dots,n$ 都输出答案。

第一行一个正整数 $T$ 表示数据组数。 对于每组数据，第一行一个正整数 $n$ 表示序列长度，第二行 $n$ 个正整数表示 $a[1\dots n]$ 。

对于每组数据，输出一行 $n$ 个数，第 $i$ 个数表示 $k=i$ 的答案。

对于 20% 的数据， $3\le n\le 15,1\le a_i\le 20$； 对于 40% 的数据， $3\le n\le 50,1\le a_i\le 20$； 对于 60% 的数据， $3\le n\le 200,1\le a_i\le 200$； 对于 100% 的数据， $1\le T\le 10,3\le n\le 500,1\le a_i\le 200$ 。