Beacon towers are built throughout and alongside the Great Wall. There was once a time when there were nnn beacon towers built from west to east for defending against the invaders. The altitude of the iii-th beacon tower, based on historical records, is aia_iai.
The defenders divide strategically all beacon towers into kkk 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 k=1,2,…,nk = 1, 2, \ldots, nk=1,2,…,n.