# 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


### Statistics

48% Solution Ratio

rafi_1703076Fastest, 0.0s

SoudipLightest, 23 MB

OnikJahanSagorShortest, 409B