Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Cutting Bamboos

By shihan04 · Limits 2s, 512 MB

There are $n$ 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 $i$ has a strength of $s_i$. But each time Khan cuts a bamboo, his axe becomes more dull. So at the $x$th time if he wants to cut the $i$th bamboo, he will need to use $x \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 $n$ $(1\le n\le 2000)$ the number of bamboos. The next line contains $n$ integers $s_i$ $(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

Discussion

Statistics


48% Solution Ratio

fire_tornadoEarliest, 4M ago

rafi_1703076Fastest, 0.0s

SoudipLightest, 23 MB

OnikJahanSagorShortest, 409B

Submit

Login to submit

Related Contests