Cutting Bamboos

shihan04 HMSPLC: কোডshock_ 2020
Limits 2s, 512 MB

There are nn 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.

  • Cut the left most bamboo
  • Cut the right most bamboo

Each bamboo ii has a strength of sis_i. But each time Khan cuts a bamboo, his axe becomes more dull. So at the xxth time if he wants to cut the iith bamboo, he will need to use x×six \times s_i 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.

Input

First line of input contains nn (1n2000)(1\le n\le 2000) the number of bamboos. The next line contains nn integers sis_i (1si105)(1\le s_i\le 10^{5}) the strength of each bamboo.

Output

You have to print the minimum number of calories to cut all the bamboos.

Sample

InputOutput
5
2 1 3 5 4
36

Submit

Login to submit.

Statistics

51% Solution Ratio
fire_tornadoEarliest, May '20
Minus_XFastest, 0.0s
SoudipLightest, 23 MB
OnikJahanSagorShortest, 409B
Toph uses cookies. By continuing you agree to our Cookie Policy.