NC223863. ForgedintheBarrens

描述

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

The defenders divide strategically all beacon towers into 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 .

输入描述

The first line contains an integer  , denoting the number of beacon towers throughout the Barrens.
The second line contains  integers   is the altitudes of the beacon towers in order.

输出描述

Output  lines, the th of which contains an integer indicating the maximum sum for .

示例1

输入:

5
1 2 3 4 5

输出:

4
3
2
1
0

示例2

输入:

5
1 2 1 2 1

输出:

1
2
2
1
0

原站题解