28ος ΠΔΠ Γ' Φάση
Εκδρομή για σκι (skitrip)

Η Κατερίνα θέλει να πάει για σκι. Το χιονοδρομικό κέντρο είναι μακριά από το σπίτι της, κι έτσι παίρνει τα πέδιλα στον ώμο και αποφασίζει να πάει στο βουνό με τον οδοντωτό σιδηρόδρομο. Ο σιδηρόδρομος κάνει στάσεις σε Ν σημεία στο βουνό. Οποιεσδήποτε δύο διαδοχικές στάσεις απέχουν μεταξύ τους ένα χιλιόμετρο. Για κάθε στάση \(i\) (όπου \(1 \le i \le N\)) γνωρίζουμε το υψόμετρο \(Y_i\) στο οποίο αυτή βρίσκεται.

Καθώς ο σιδηρόδρομος απομακρύνεται στο βουνό, η Κατερίνα μπορεί να κατέβει το πρωί σε όποια στάση θέλει, να κάνει σκι με κατεύθυνση προς τα πίσω και να επιβιβαστεί πάλι στο σιδηρόδρομο σε κάποια προηγούμενη στάση, όταν αυτός θα επιστρέφει το απόγευμα, ώστε να γυρίσει στο σπίτι της. Όμως, για να μπορέσει να κάνει σκι, η στάση που θα κατέβει πρέπει να μην είναι σε χαμηλότερο υψόμετρο από εκείνην που θα επιβιβαστεί και πάλι.

Στην Κατερίνα αρέσει πολύ το σκι. Βοηθήστε τη να βρει τη μεγαλύτερη διαδρομή που μπορεί να κάνει.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI (Pascal, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα \(N\) και \(Y_i\) και θα υπολογίζει το μήκος της μεγαλύτερης διαδρομής που μπορεί να κάνει η Κατερίνα.

Αρχεία Εισόδου

Το αρχείο εισόδου με όνομα skitrip.in είναι αρχείο κειμένου που περιέχει δύο γραμμές.

• Η πρώτη γραμμή περιέχει έναν μόνο ακέραιο αριθμό \(N\), το πλήθος των σημείων στα οποία κάνει στάση ο σιδηρόδρομος.
• Η δεύτερη γραμμή περιέχει \(N\) ακέραιους αριθμούς \(Y_i\) (τα υψόμετρα των σημείων στάσης) (όπου \(1 \le i \le N\)) χωρισμένους ανά δύο με ένα κενό διάστημα.

Αρχεία εξόδου

Το αρχείο εξόδου με όνομα skitrip.out είναι αρχείο κειμένου αποτελούμενο από μία μόνο γραμμή που πρέπει να περιέχει ακριβώς έναν ακέραιο αριθμό: το μήκος της μεγαλύτερης διαδρομής που μπορεί να κάνει η Κατερίνα.

Αν δεν υπάρχει καμία έγκυρη διαδρομή (γιατί τα υψόμετρα των σημείων στάσης μειώνονται, όσο κινείται ο σιδηρόδρομος), τότε η απάντηση πρέπει να είναι μηδέν.

Παράδειγμα αρχείων εισόδου - εξόδου

skitrip.in	skitrip.out
16 78 88 64 94 17 91 57 69 38 62 13 17 35 15 20 15	10

Εξήγηση: Η Κατερίνα μπορεί να κατέβει στη 15η στάση, που έχει υψόμετρο \(Y_{15} = 20\). Από εκεί, μπορεί να κάνει σκι προς τα πίσω μέχρι την 5η στάση, που έχει υψόμετρο \(Y_5 = 17\). Η διαδρομή αυτή είναι η μεγαλύτερη που μπορεί να κάνει και έχει μήκος \(15−5 = 10\) χιλιόμετρα.

Όρια

• \(1 \le Y_i \le 10^9\).
• Για περιπτώσεις ελέγχου συνολικής αξίας 40%, θα είναι: \(1 \le N \le 10^4\).
• Για περιπτώσεις ελέγχου συνολικής αξίας 80%, θα είναι: \(1 \le N \le 10^6\).
• Για περιπτώσεις ελέγχου συνολικής αξίας 100%, θα είναι: \(1 \le N \le 2\times 10^6\).

Μέγιστος χρόνος εκτέλεσης: 1 sec
Μέγιστη διαθέσιμη μνήμη: 128 MB