410444: GYM104022 B The Great Wall

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. The Great Walltime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Beacon towers are built throughout and alongside the Great Wall. There was once a time when there were $$$n$$$ beacon towers built from west to east for defending against the invaders. The altitude of the $$$i$$$-th beacon tower, based on historical records, is $$$a_i$$$.

The defenders divide strategically all beacon towers into $$$k$$$ parts where each part contains several, but at least one, consecutive beacon towers. The scale of an individual part is given by the difference between the highest and the lowest altitudes of beacon towers, and the most sensible partition maximizes the sum of scales of all parts.

As a historian, you are dying to know the maximum sums of scales for every $$$k = 1, 2, \ldots, n$$$.

Input

The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^4)$$$, denoting the number of beacon towers alongside the Great Wall.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, where the $$$i$$$-th integer $$$a_i$$$ $$$(1 \leq a_i \leq 10^5)$$$ is the altitude of the $$$i$$$-th beacon tower.

Output

Output $$$n$$$ lines, the $$$i$$$-th of which contains an integer indicating the maximum sum for $$$k = i$$$.

ExamplesInput
5
1 2 3 4 5
Output
4
3
2
1
0
Input
5
1 2 1 2 1
Output
1
2
2
1
0

加入题单

上一题 下一题 算法标签: