Background

Special for beginners, ^_^

Description

serling公司购买长钢条，然后将其切割为短钢条出售。钢条的长度均为整英寸。

假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。

说明

切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案, 使得销售收益最大,最优解可能完全不需要切割。

Format

Input

输入文件一共2行，

第1行一个整数n（n<=50000），表示有n个价格；

第2行有n个非负整数Pi(Pi<=50000)，分别表示长度为1——n的钢材价格；

Output

n个整数，分别表示长度为1——n的钢材最大收益。

Samples

10
1 5 8 9 10 17 17 20 24 30

1 5 8 10 13 17 18 22 25 30

Limitation

1s, 1024KiB for each test case.