Time Limit: 3 Sec  

Memory Limit: 128 MB

Submit: 622  

Solved: 20

[ ][ ][ ]

Description

As we all know, There is a hero called Priestess of the Moon(POM), which has a

passive ability named 

Trueshot Aura

. It can add other units some ranged attacks . Fanfan love the Human very much, and he will battle with a Night Elf everyday , because he thinks the Night Elf can’t attack his tower easily .But today , he met a Night Elf player , who use POM as his first hero, and had lots of Archers . Fanfan use the

Mountain King to kill the Archers ,and don’t know how many health he need to kill all the Archers .Could you help him ?

        To make the problem simple , we assume that all the Archers stand in a line , they have different attacks , if Fanfan kills the ith Archer , the (i+1)th and the (i-1)th Archer will help to attack Fanan by their own attacks . There are N Archers , and Fanfan wants to know the least damage he will get to kill all the Archers .

Input

First line contains an integer N (0<N<200), means there are N Archers .

Then the next line contains N integers ai(0<ai<100000) means that the ith Archers have ai attacks . 

Output

An integer means the least damage Fanfan will get.

Sample Input

310 100 10

Sample Output

150

HINT

Yifan first kill the second Archer , get 100+10+10 demages , and then kill the first one ,get 10+10 demages and finally kill the third one and get 10 demages so , he get 150 demage

看了其他人的思路整理出来。相似题目：POJ1651:Multiplication Puzzle

# include 
     
      # include 
      
       int min(int a, int b){    return a