There are stones, numbered from to . For each , the height of the -th stone is . The frog initially sits on stone . It repeats the following action several times to reach stone : if the frog is on stone , it can jump either to stone or to stone . The cost of moving from the -th to the -th stone is .
Find the minimum cost of moving the frog to stone .
The first line contains the number of stones . The second line contains integers .
Print the minimum cost of moving the frog to stone .