Beacon towers are built throughout and alongside the Great Wall. 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 strategically divide 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 relaxable partition minimizes the sum of scales of all parts.

As a historian, you are dying to know the minimum sums of scales for every .

The first line contains an integer  (), denoting the number of beacon towers alongside the Great Wall.

The second line contains  integers , where the -th integer  () is the altitude of the -th beacon tower.

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

5
1 2 3 4 5

4
3
2
1
0

5
1 2 1 2 1

1
1
1
1
0