Αρχική > 38ος ΠΔΠ

38ος ΠΔΠ Α' Φάση
Κήπος με μπαμπού (bamboo)

Ο Τάκης έχει έναν μικρό κήπο τον οποίο φροντίζει για να χαλαρώνει και να ξεφεύγει λίγο από την ένταση της δουλειάς στην πιτσαρία. Στον κήπο υπάρχουν \(N\) μπαμπού. Τα ύψη τους συμβολίζονται με τους θετικούς ακέραιους \(h_1, h_2, \ldots, h_N\). Ο Τάκης έχει βαρεθεί να έχει τόσα μπαμπού στον κήπο του και θέλει να τα κόψει. Για να το κάνει αυτό, ακολουθεί την εξής διαδικασία:

  1. Καταγράφει το μέγιστο ύψος \(H\) από όλα τα μπαμπού του.
  2. Στη συνέχεια κόβει όλα τα μπαμπού του που έχουν ύψος \(H\) (δηλαδή μηδενίζει το ύψος τους). Αν μετά από αυτό το βήμα και τα \(N\) μπαμπού έχουν μηδενικό ύψος, σταματάει. Αλλιώς, περιμένει την επόμενη ημέρα και επαναλαμβάνει από το βήμα 1.

Ως καλός φίλος του Τάκη, ανησυχείτε ότι με αυτόν τον τρόπο μπορεί να χρειαστεί να κόβει μπαμπού για πολλά χρόνια, οπότε για να τον μεταπείσετε, θέλετε να βρείτε πόσες μέρες θα χρειαζόταν συνολικά για αυτή τη διαδικασία.

Δεδομένα εισόδου (stdin)

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(N\): το πλήθος των μπαμπού στον κήπο του Τάκη. Η δεύτερη γραμμή περιέχει \(N\) ακέραιους αριθμούς \(h_1, h_2, \ldots, h_N\): τα ύψη των μπαμπού.

Δεδομένα εξόδου (stdout)

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: το πλήθος των ημερών που θα χρειαζόταν ο Τάκης για να κόψει όλα τα φυτά του κήπου του με την παραπάνω διαδικασία.

Παράδειγμα εισόδου-εξόδου

stdin stdout
5
1 7 3 7 3		 3

Εξήγηση παραδείγματος: Ο Τάκης θα έκοβε τα μπαμπού του ως εξής:

  • Ημέρα 1η: Το μέγιστο ύψος είναι 7. Συνεπώς, ο Τάκης κόβει το 2ο και το 4ο μπαμπού.
  • Ημέρα 2η: Τώρα, το μέγιστο ύψος είναι 3. Για αυτό, ο Τάκης κόβει το 3ο και το 5ο μπαμπού.
  • Ημέρα 3η: Το μέγιστο ύψος είναι 1. Ο Τάκης κόβει το 1ο μπαμπού και τώρα όλα τα μπαμπού έχουν κοπεί πλέον, οπότε σταματάει.

Επομένως, ο Τάκης θα χρειαζόταν 3 ημέρες.

Περιορισμοί

  • \(1 \leq N \leq 200.000\),
  • \(1 \leq h_i \leq 10^9\).

Υποπροβλήματα

  1. (13 βαθμοί) \(N = 2\)
  2. (17 βαθμοί) Όλα τα μπαμπού έχουν διαφορετικά ύψη μεταξύ τους
  3. (19 βαθμοί) \(N \leq 5.000\)
  4. (23 βαθμοί) \(h_i \leq 10^5\), για κάθε \(i\) (όπου \(1 \leq i \leq N\))
  5. (28 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.

Παρατηρήσεις

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