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 divide strategically all beacon towers into parts where each part contains several, but at least one, consecutive beacon towers. To fully defend against the invaders, to each part a team of defenders should be assigned, the cost of which is given by the highest altitudes of beacon towers in that part.

As a historian, you are dying to know the minimum costs of assignments for every .