Po

Ο Tinky Winky άφησε μια ακολουθία από n μηδενικά στο Tubbytronic Superdome και έφυγε για μια βόλτα με το Dipsy. Όταν γύρισε, είδε ότι έχει γίνει ένα μια κακή πράξη. Η σειρά άλλαξε και ο Po χαμογελούσε πονηρά στη γωνία του δωματίου.

 Ω αγαπητέ! Po, τί έκανες?! – ρώτησε ο Tinky Winky τρομαγμένος.

 Βελτίωσα τη σειρά! – απάντησε ο Po.

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

 Πόσες βελτιώσεις έχεις κάνει Po; – ρώτησε ο Laa-Laa.

 Πραγματικά δεν ξέρω! Είμαι σίγουρος ότι έκανα τον ελάχιστο δυνατό αριθμό βελτιώσεων για να λάβω αυτήν τη σειρά! – είπε εξαντλημένος ο Po.

 Τότε σίγουρα πρέπει να είναι ~m~! – ισχυρίστηκε ο Noo-Noo¹.

Τι αριθμό είπε ο Noo-Noo;

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο ~n\;(1 \le n \le 100,000)~, το μήκος της ακολουθίας.

Η δεύτερη γραμμή περιέχει ~n~, μη αρνητικούς ακέραιους, ~a_i\;(0 \le a_i \le 10^9)~, την ακολουθία μετά τις βελτιώσεις του Po.

Έξοδος

Τυπώνετε το ~m~, τον ελάχιστο δυνατό αριθμό βελτιώσεων.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30 πόντων, ισχύει ~1 \le n \le 1000~.

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

input

3
2 2 2

output

1

input

5
2 3 3 3 2

output

2

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

Ο Po αύξησε πρώτα όλα τα στοιχεία της ακολουθίας κατά 2 και στη συνέχεια αύξησε τα τρία μεσαία κατά 1.

input

6
1 2 3 2 1 3

output

4

Noo-Noo είναι το κατοικίδιο της ηλεκτρικής σκούπας της Teletubies