Guma

Ένα εργοστάσιο που ονομάζεται Gumi-Gumi είναι αφιερωμένο στην κατασκευή ελαστικών. Η σκαλιστική μηχανή τους είναι υπεύθυνη για τη χάραξη γεμιστικών στο ελαστικό. Το ελαστικό έχει ~N~ κατακόρυφα γεμιστικά που χωρίζουν το ελαστικό σε ~N+1~ κάθετα μέρη. Γίνονται οριζόντιες τομές σε κάθε κατακόρυφο τμήμα έτσι ώστε όλα τα μέρη που αποτελούν το κατακόρυφο τμήμα να είναι ίσου μεγέθους. Το μηχάνημα μπορεί να κάνει γεμιστικά σε ένα ή περισσότερα όχι απαραίτητα συνεχόμενα κάθετα τμήματα σε μία τομή, αλλά μπορεί να κόψει μόνο σε ευθεία γραμμή.

Ένα παράδειγμα στρατηγικής κοπής ελαστικών, που αντιστοιχεί στο τρίτο δείγμα δοκιμής.

Η υψηλότερη και η χαμηλότερη γραμμή αντιπροσωπεύουν μια πλήρη οριζόντια τομή, ενώ η πρώτη και η τελευταία κάθετη γραμμή είναι τα άκρα του ελαστικού.

Σας δίνεται το σχήμα του ελαστικού. Το καθήκον σας είναι να υπολογίσετε τον ελάχιστο δυνατό αριθμό κοπών που απαιτούνται για να αποκτήσετε ένα τέτοιο σχήμα.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(1 \leq N \leq 100\,000)~.

Κάθε μία από τις ακόλουθες ~N+1~ γραμμές περιέχει έναν ακέραιο αριθμό ~a_i\;(1 \leq a_i \leq 100\,000)~, που αντιπροσωπεύει τον αριθμό των τμημάτων από τα οποία θα πρέπει να αποτελείται το ~i~-οστό κατακόρυφο τμήμα.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να αποτελείται από τον ελάχιστο απαιτούμενο αριθμό κοπών.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας ~20~% των συνολικών πόντων, το ~N~ δεν θα υπερβαίνει τους 100.

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

input

1
2
5

output

5

input

2
3
7
14

output

15

input

9
4
8
4
1
2
2
2
8
4
2

output

7