Nikola

Παρά τη θέλησή του, ο Nikola έγινε ο κύριος χαρακτήρας ενός παιχνιδιού. Το παιχνίδι παίζεται σε μια σειρά από ~N~ τετράγωνα, αριθμημένα από ~1~ έως ~N~. Ο Νικόλα βρίσκεται αρχικά στο τετράγωνο ~1~ και μπορεί να μεταπηδήσει σε άλλα τετράγωνα. Το πρώτο άλμα του Nikola πρέπει να γίνει στο τετράγωνο ~2~. Κάθε επόμενο άλμα πρέπει να ικανοποιεί δύο περιορισμούς:

• Εάν το άλμα είναι προς την εμπρός κατεύθυνση, πρέπει να είναι κατά ένα τετράγωνο μεγαλύτερο από το προηγούμενο άλμα.
• Εάν το άλμα είναι προς την πίσω κατεύθυνση, πρέπει να είναι ακριβώς το ίδιο μήκος με το προηγούμενο άλμα.

Για παράδειγμα, μετά το πρώτο άλμα (όταν βρίσκεται στο τετράγωνο ~2~), ο Nikola μπορεί να μεταπηδήσει πίσω στο τετράγωνο ~1~ ή προς τα εμπρός στο τετράγωνο ~4~.

Κάθε φορά που μπαίνει σε ένα τετράγωνο, ο Nikola πρέπει να πληρώνει τέλος εισόδου. Στόχος του Nikola είναι να φτάσει από το τετράγωνο ~1~ στο τετράγωνο ~N~ όσο πιο φθηνά γίνεται. Γράψτε ένα πρόγραμμα που να καθορίζει το μικρότερο συνολικό κόστος για τον Nikola, για να φτάσει στο τετράγωνο ~N~.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~N, 2 \le N \le 1000~, τον αριθμό των τετραγώνων.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει το τέλος εισόδου για ένα τετράγωνο, θετικό ακέραιο μικρότερο από ~500~. Τα τέλη εισόδου θα δίνονται με σειρά για τα τετράγωνα ~1~ έως ~N~.

Έξοδος

Τυπώστε το μικρότερο συνολικό κόστος για τον Nikola για να φτάσει στο τετράγωνο ~N~.

Παραδείγματα

input

6
1
2
3
4
5
6

output

12

Επεξήγηση του 1ου παραδείγματος:

Στο πρώτο παράδειγμα, αφού πηδήξει στο τετράγωνο ~2~, ο Nikola πηδάει πίσω στο τετράγωνο ~1~. Από εκεί μπορεί να πηδήξει στο τετράγωνο ~3~ και στη συνέχεια στο ~6~.

input

8
2
3
4
3
1
6
1
4

output

14