提示: 欢迎访问OurACM平台。
Problem 2136 取糖果

Accept: 194    Submit: 568
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

有N个袋子放成一排,每个袋子里有一定数量的糖果,lzs会随机选择连续的几个袋子,然后拿走这些袋子中包含最多糖果的袋子。现问你,在选择x个袋子的情况下,lzs最坏情况下,也就是最少会拿到多少个糖果?对于x取值为1到n都分别输出答案。

Input

第一行一个整数T,表示有T组数据。

每组数据先输入一行一个整数N(1<=N<=100000),表示袋子数,接下来一行输入N个正整数,输入的第i个数表示第i个袋子所装的糖果数。

Output

每组数据输出n行,第i行表示lzs随机取连续的i个袋子时的最坏情况下能拿到的糖果数。

Sample Input

1 5 1 3 2 4 5

Sample Output

1 3 3 4 5

Submit  Back  Status  Discuss