Problem 3025 --Three Investigators

3025: Three Investigators

正确率: $0.00\%$ 下一题

Time Limit	$5$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$1$	正确数量	$0$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签

Description

Chitanda owns a sequence a1,a2,…,ana1,a2,…,an with nn integers, and she wants to play a game with Skywalkert.

First, Chitanda will select a parameter kk and remove ak+1,ak+2,…,anak+1,ak+2,…,an. Thus there will be exactly kk integers in sequence aa.

Then Skywalkert can select a subsequence of aa and remove it from aa. Assume the selected subsequence is ap1,ap2,…,apmap1,ap2,…,apm, he should ensure p1<p2<⋯<pmp1<p2<⋯<pm and ap1≤ap2≤⋯≤apmap1≤ap2≤⋯≤apm.

Skywalkert can do the above operation for no more than 55 times. His score is the sum of all the integers selected by him in these no more than 55 operations.

Given the parameter kk selected by Chitanda, write a program to help Skywalkert maximize his score.

Input

The first line of the input contains an integer T(1≤T≤10000)T(1≤T≤10000), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤100000)n(1≤n≤100000) in the first line, denoting the length of aa.

In the second line, there are nn integers a1,a2,...,an(1≤ai≤109)a1,a2,...,an(1≤ai≤109), denoting the sequence.

It is guaranteed that ∑n≤500000∑n≤500000.

Output

For each test case, print a single line containing nn integers s1,s2,…,sns1,s2,…,sn , where sisidenotes the maximum score of Skywalkert when k=ik=i.

Sample Input复制

1
8
8 7 6 5 1 3 2 4

Sample Output复制

8 15 21 26 27 30 30 34

赛题来源/所属竞赛 2019 Multi-University Training Contest 6 N/A

竞赛编号	竞赛名称	竞赛时间	访问比赛

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战	淡意的温柔	591126	2020-06-06 08:24:46