28ος ΠΔΠ Καμπ (κοινά)
Βιβλιοφάγοι (bookeaters)

Σε ένα σχολείο υπάρχουν \(N\) παιδιά. Το αξιοπερίεργο με αυτό το σχολείο, είναι ότι όλα τα παιδιά είναι βιβλιοφάγοι: τους αρέσει πολύ να διαβάζουν βιβλία. Τώρα που έρχονται οι καλοκαιρινές διακοπές, τα παιδιά ανυπομονούν να διαβάσουν καινούργια βιβλία στον ελεύθερο χρόνο που θα έχουν. Ας υποθέσουμε ότι κάθε παιδί έχει ένα καινούργιο βιβλίο, που ούτε το ίδιο ούτε κανένα άλλο παιδί δεν έχει διαβάσει. Προκειμένου να διαβάσουν τα παιδιά όσο περισσότερα καινούργια βιβλία γίνεται, αποφασίζουν να χωριστούν σε παρέες και να περάσουν τις διακοπές τους μαζί. Αν μια παρέα αποτελείται από \(K\) παιδιά, τότε θα υπάρχουν σε αυτήν \(K\) καινούργια βιβλία και κάθε παιδί θα τα διαβάσει όλα, μέχρι το φθινόπωρο. Για τα παιδιά, όσο πιο μεγάλες είναι οι παρέες, τόσο το καλύτερο!

Τα παιδιά λένε την ιδέα τους στο διευθυντή του σχολείου, ο οποίος τη βρίσκει καταπληκτική και αποφασίζει να τα βοηθήσει να την πραγματοποιήσουν. Γρήγορα όμως βλέπει ότι υπάρχει μία δυσκολία που τα παιδιά δεν έχουν προβλέψει. Δεν είναι εύκολο να βρεθούν δωμάτια για να φιλοξενήσουν πολύ μεγάλες παρέες, κατά τη διάρκεια του καλοκαιριού. Ο διευθυντής γρήγορα καταλαβαίνει ότι, για να μπορέσουν να εφαρμόσουν το σχέδιό τους, τα παιδιά θα πρέπει να χωριστούν σε όσο περισσότερες ομάδες γίνεται. Τα παιδιά όμως στενοχωριούνται, γιατί έτσι θα διαβάσουν λιγότερα βιβλία. Σε μια προσπάθεια να βρει κάποια λύση, ο διευθυντής ρωτάει κάθε παιδί πόσα βιβλία θα ήταν ευχαριστημένο, αν διάβαζε φέτος το καλοκαίρι.

Γράψτε ένα πρόγραμμα που, βάσει των απαντήσεων των παιδιών, να υπολογίζει το μέγιστο δυνατό πλήθος ομάδων που μπορούν να σχηματιστούν ώστε όλα τα παιδιά να είναι ευχαριστημένα. Αν υπάρχουν περισσότεροι δυνατοί τρόποι να χωριστούν τα παιδιά στο μέγιστο δυνατό πλήθος ομάδων, βρείτε ποιος είναι ο τρόπος που ελαχιστοποιεί το πλήθος των παιδιών της μεγαλύτερης ομάδας.

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

Αρχεία Εισόδου (bookeaters.in):

Η πρώτη γραμμή της εισόδου θα περιέχει ένα φυσικό αριθμό \(N\): το πλήθος των παιδιών του σχολείου. Οι επόμενες \(N\) γραμμές θα περιέχουν ακριβώς \(N\) φυσικούς αριθμούς \(B_1, \ldots , B_N\), έναν φυσικό η καθεμία: τις απαντήσεις των παιδιών. Δηλαδή, το \(i\)-οστό παιδί που ρώτησε ο διευθυντής απάντησε ότι θα είναι ευχαριστημένο αν φέτος διαβάσει τουλάχιστον \(B_i\) βιβλία.

Αρχεία Εξόδου (bookeaters.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που θα περιέχει δύο φυσικούς αριθμούς \(M\) και \(K\), χωρισμένους με ένα κενό μεταξύ τους. Το \(M\) θα είναι το μέγιστο δυνατό πλήθος ομάδων που μπορούν να σχηματιστούν έτσι ώστε όλα τα παιδιά να είναι ευχαριστημένα. Για αυτό το μέγιστο \(M\), το \(K\) θα είναι το ελάχιστο πλήθος παιδιών που μπορεί να έχει η μεγαλύτερη ομάδα.

Παράδειγμα Αρχείου Εισόδου - Εξόδου:

bookeaters.in	bookeaters.out
5 2 1 2 2 3	2 3

Εξήγηση παραδείγματος: Το μέγιστο πλήθος ομάδων που μπορούν να σχηματιστούν είναι \(M = 2\). (Δεν υπάρχει τρόπος να σχηματιστούν τρεις ομάδες και να είναι όλα τα παιδιά ευχαριστημένα.) Ένας τρόπος να σχηματιστούν δύο ομάδες είναι να πάει μόνο του στη μία ομάδα το παιδί που είναι ευχαριστημένο με ένα βιβλίο, και στην άλλη όλα τα υπόλοιπα. Τότε, το πλήθος των παιδιών της μεγαλύτερης ομάδας θα είναι \(4\). Ένας άλλος τρόπος είναι να μεταφερθεί στην πρώτη ομάδα (μαζί με το παιδί που είναι ευχαριστημένο με ένα βιβλίο) και ένα από τα παιδιά που είναι ευχαριστημένα με δύο βιβλία. Τότε, το πλήθος των παιδιών της μεγαλύτερης ομάδας θα είναι \(3\). Δεν είναι δυνατό να σχηματιστούν δύο ομάδες και η μεγαλύτερη να έχει μικρότερο πλήθος παιδιών από \(3\), επομένως \(K = 3\).

Περιορισμοί

• \(1 \leq N \leq 1.000.000\).
• \(1 \leq B_i \leq N\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(64\) MB.