There are stones, numbered
,
,
,
. For each
, the height of Stone
is
.
There is a frog who is initially on Stone . He will repeat the following action some number of times to reach Stone
:
- If the frog is currently on Stone
, jump to Stone
or Stone
. Here, a cost of
is incurred, where
is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches Stone .

Constraints
- All values in input are integers.
Input Specification
The first line of input will contain an integer .
The second line of input will contain spaced integers,
, the height of stone
.
Output Specification
Output a single integer, the minimum possible total cost incurred.
Sample Input 1
4
10 30 40 20
Sample Output 1
30
Sample Input 2
2
10 10
Sample Output 2
0
Sample Input 3
6
30 10 60 10 60 50
Sample Output 3
40
Sample Explanations
For the first sample, we can follow path , the total cost incurred would be
.
For the second sample, we can follow the path , with the total cost incurred being
.
In the last sample, we follow the path , the total cost incurred would be
.
Comments