There are bamboos in a row. Khan the bamboo cutter is going to cut them all one by one. He can do one of the following operations at a time.
Each bamboo has a strength of . But each time Khan cuts a bamboo, his axe becomes more dull. So at the th time if he wants to cut the th bamboo, he will need to use calories. Khan doesn't want to use too many calories. So he asks your help to find out the lowest calorie he can use to cut all the bamboos.
First line of input contains the number of bamboos. The next line contains integers the strength of each bamboo.
You have to print the minimum number of calories to cut all the bamboos.
5 2 1 3 5 4