Baloni

Υπάρχουν N μπαλόνια που επιπλέουν στον αέρα σε ένα μεγάλο δωμάτιο, παρατεταγμένα από αριστερά προς τα δεξιά. Στον νεαρό Perica αρέσει να παίζει με τα βέλη και να εξασκεί τις κυνηγετικές του ικανότητες. Εκτοξεύει ένα βέλος από την αριστερή προς τη δεξιά πλευρά του δωματίου από ένα αυθαίρετο ύψος που επιλέγει. Το βέλος κινείται από αριστερά προς τα δεξιά, σε επιλεγμένο ύψος H μέχρι να βρει ένα μπαλόνι. Τη στιγμή που ένα βέλος αγγίζει ένα μπαλόνι, το μπαλόνι σκάει και εξαφανίζεται και το βέλος συνεχίζει την πορεία του από αριστερά προς τα δεξιά σε ύψος μειωμένο κατά 1. Επομένως, εάν το βέλος κινούνταν στο ύψος H, αφού σκάσει το μπαλόνι ταξιδεύει σε ύψος Η-1.

Ο στόχος του ήρωά μας είναι να σκάσει όλα τα μπαλόνια χρησιμοποιώντας όσο το δυνατόν λιγότερα βέλη.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(1 \leq N \leq 1\,000\,000)~.
Η δεύτερη γραμμή εισόδου περιέχει έναν πίνακα ~N~ ακεραίων ~H_i~.
Κάθε ακέραιος ~H_i\;(1 \leq H_i \leq 1\,000\,000)~ είναι το ύψος στο οποίο επιπλέει το ~i~-οστό μπαλόνι, αντίστοιχα από αριστερά προς τα δεξιά.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τις ελάχιστες φορές που χρειάζεται ο Pero να ρίξει ένα βέλος έτσι ώστε να σκάσουν όλα τα μπαλόνια.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 40%, θα έχει ~N \leq 5\,000~.

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

input

5
2 1 5 4 3

output

2

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

Ο ήρωάς μας εκτοξεύει το βέλος στο ύψος 5 - το οποίο καταστρέφει το ~[5,\;4,\;3]~ και ρίχνει ένα βέλος στο ύψος 2 - το οποίο καταστρέφει το ~[2,\;1]~.

input

5
1 2 3 4 5

output

5

input

5
4 5 2 1 4

output

3