# Σπανιότατα Έντομα
Υπάρχουν $N$ έντομα, αριθμημένα από το $0$ μέχρι το $N - 1$, που τρέχουν γύρω από το σπίτι του Pak Blangkon. Κάθε έντομο έχει έναν **τύπο**, ο οποίος είναι ένας ακέραιος αριθμός μεταξύ του $0$ και $10^9$ συμπεριλαμβανομένων. Πολλά έντομα μπορούν να έχουν τον ίδιο τύπο.
Υποθέστε ότι τα έντομα ομαδοποιούνται ανά τύπο.
Ορίζουμε την συχνότητα (cardinality) του **πιο συχνού** τύπου εντόμου ως τον αριθμό των εντόμων της ομάδας με το μεγαλύτερο πλήθος εντόμων.
Παρομοίως, την συχνότητα του **σπανιότερου** τύπου εντόμου ως τον αριθμός των εντόμων της ομάδας με τον μικρότερο πλήθος εντόμων.
Για παράδειγμα, υποθέστε ότι υπάρχουν $11$ έντομα, των οποίων οι τύποι είναι $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$. Σε αυτή την περίπτωση, η συχνότητα του **πιο συχνού** τύπου εντόμου είναι $3$. Οι ομάδες με το μεγαλύτερο πλήθος εντόμων είναι τύπου $9$ και τύπου $11$, καθεμία αποτελούμενη από $3$ έντομα. Η συχνότητα του **σπανιότερου** τύπου εντόμου είναι $1$. Οι ομάδες με το μικρότερο πλήθος εντόμων είναι τύπου $7$, τύπου $0$ και τύπου $100$, καθεμία αποτελούμενη από $1$ έντομο.
Ο Pak Blangkon δεν γνωρίζει τον τύπο κανενός εντόμου.
Έχει ένα μηχάνημα με μόνο ένα κουμπί που μπορεί να δώσει κάποιες πληροφορίες για τους τύπους των εντόμων. Αρχικά, το μηχάνημα είναι άδειο. Για να χρησιμοποιήσετε το μηχάνημα, μπορούν να εκτελεστούν τρεις τύποι λειτουργιών:
1. Μετακινήστε ένα έντομο μέσα στο μηχάνημα.
1. Μετακινήστε ένα έντομο έξω από το μηχάνημα.
1. Πατήστε το κουμπί στο μηχάνημα.
Κάθε τύπος λειτουργίας μπορεί να εκτελεστεί το πολύ $40\;000 $ φορές.
Κάθε φορά που πατιέται το κουμπί, το μηχάνημα αναφέρει την συχνότητα του **πιο συχνού** τύπου εντόμου, λαμβάνοντας υπόψη μόνο τα έντομα μέσα στο μηχάνημα.
Ο στόχος σας είναι να προσδιορίσετε την συχνότητα του **σπανιότερου** τύπου εντόμου μεταξύ όλων των $N$ εντόμων στο σπίτι του Pak Blangkon χρησιμοποιώντας το μηχάνημα. Επιπλέον, σε κάποια υποπροβλήματα (subtask), η βαθμολογία σας εξαρτάται από τον μέγιστο αριθμό λειτουργιών κάποιου από τους τρεις προηγούμενους τύπους (δείτε τα υποπροβλήματα για λεπτομέρειες).
## Λεπτομέρειες υλοποίησης
Υλοποιείστε την ακόλουθη συνάρτηση:
```
int min_cardinality(int N)
```
* $N$: ο αριθμός των εντόμων.
* Αυτή η συνάρτηση πρέπει να επιστρέφει την συχνότητα του **σπανιότερου** τύπου εντόμου μεταξύ όλων των $N$ εντόμων στο σπίτι του Pak Blangkon.
* Αυτή η συνάρτηση καλείται ακριβώς μία φορά.
Η παραπάνω συνάρτηση μπορεί να καλέσει τις ακόλουθες συναρτήσεις:
```
void move_inside(int i)
```
* $i$: ο δείκτης του εντόμου που θα μπει μέσα στο μηχάνημα. Η τιμή του $i$ πρέπει να είναι μεταξύ του $0$ και του $N - 1$ συμπεριλαμβανομένων.
* Εάν αυτό το έντομο βρίσκεται ήδη μέσα στο μηχάνημα, η κλήση δεν έχει καμία επίδραση στο σύνολο των εντόμων του μηχανήματος. Ωστόσο, εξακολουθεί να υπολογίζεται ως ξεχωριστή κλήση συνάρτησης.
* Αυτή η συνάρτηση μπορεί να κληθεί το πολύ $40\;000$ φορές.
```
void move_outside(int i)
```
* $i$: ο δείκτης του εντόμου που θα βγεί έξω από το μηχάνημα. Η τιμή του $i$ πρέπει να είναι μεταξύ του $0$ και του $N - 1$ συμπεριλαμβανομένων.
* Εάν αυτό το έντομο βρίσκεται ήδη έξω από το μηχάνημα, η κλήση δεν έχει καμία επίδραση στο σύνολο των εντόμων του μηχανήματος. Ωστόσο, εξακολουθεί να υπολογίζεται ως ξεχωριστή κλήση.
* Αυτή η συνάρτηση μπορεί να κληθεί το πολύ $40\;000$ φορές.
```
int press_button()
```
* Αυτή η συνάρτηση επιστρέφει την συχνότητα του **πιο συχνού** τύπου εντόμου, λαμβάνοντας υπόψη μόνο τα έντομα μέσα στο μηχάνημα.
* Αυτή η συνάρτηση μπορεί να κληθεί το πολύ $40\;000$ φορές.
* Ο βαθμολογητής ** δεν είναι προσαρμοστικός (not adaptive)**. Δηλαδή, οι τύποι όλων των $N$ εντόμων είναι καθορισμένη πριν τη κλήση της `min_cardinality`.
## Παράδειγμα
Εξετάστε ένα σενάριο στο οποίο υπάρχουν $6$ έντομα των τύπων $[5, 8, 9, 5, 9, 9]$ αντίστοιχα.
Η συνάρτηση 'min_cardinality' καλείται με τον ακόλουθο τρόπο:
```
min_cardinality(6)
```
Η συνάρτηση μπορεί να καλέσει την «move_inside», την «move_outside» και την «press_button» ως εξής.
Κλήση | Επιστρεφόμενη τιμή | Έντομα στο μηχάνημα | Τύποι εντόμων στο μηχάνημα
:---------------:|:--------------:|:---------------- ---------:|:--------------------------------:
| | $\\{\\}$ | $[]$
`move_inside(0)` | | $\\{0\\}$ | $[5]$
`press_button()` | $1$ | $\\{0\\}$ | $[5]$
`move_inside(1)` | | $\\{0, 1\\}$ | $[5, 8]$
`press_button()` | $1$ | $\\{0, 1\\}$ | $[5, 8]$
`move_inside(3)` | | $\\{0, 1, 3\\}$ | $[5, 8, 5]$
`press_button()` | $2$ | $\\{0, 1, 3\\}$ | $[5, 8, 5]$
`move_inside(2)` | | $\\{0, 1, 2, 3\\}$ | $[5, 8, 9, 5]$
`move_inside(4)` | | $\\{0, 1, 2, 3, 4\\}$ | $[5, 8, 9, 5, 9]$
`move_inside(5)` | | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$
`press_button()` | $3$ | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$
`move_inside(5)` | | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$
`press_button()` | $3$ | $\\{0, 1, 2, 3, 4, 5\\}$ | $[5, 8, 9, 5, 9, 9]$
`move_outside(5)`| | $\\{0, 1, 2, 3, 4\\}$ | $[5, 8, 9, 5, 9]$
`press_button()` | $2$ | $\\{0, 1, 2, 3, 4\\}$ | $[5, 8, 9, 5, 9]$
Σε αυτό το σημείο, υπάρχουν επαρκείς πληροφορίες για να συμπεράνουμε πως η συχνότητα του πιο σπάνιου τύπου εντόμου είναι $1$. Επομένως, η συνάρτηση «min_cardinality» πρέπει να επιστρέψει $1$.
Σε αυτό το παράδειγμα, η "move_inside" καλείται $7$ φορές, η "move_outside" καλείται $1$ φορά και η "press_button" καλείται $6$ φορές.
## Περιορισμοί
* $2 \le N \le 2000$
## Υποπροβλήματα
1. (10 βαθμοί) $N \le 200$
1. (15 βαθμοί) $N \le 1000$
1. (75 βαθμοί) Κανένας επιπλέον περιορισμός.
Εάν σε οποιαδήποτε από τα αρχεία ελέγχου (test cases), οι κλήσεις των συναρτήσεων «move_inside», «move_outside» ή «press_button» δεν συμβαδίζουν με τους περιορισμούς που περιγράφονται στις λεπτομέρειες υλοποίησης ή η τιμή που επιστρέφει η «min_cardinality» είναι λάθος, η βαθμολογία για αυτό το υποπρόβλημα (subtask) θα είναι $0$.
Έστω $q$ το **μέγιστο** των ακόλουθων τριών τιμών : ο αριθμός των κλήσεων της "move_inside", ο αριθμός των κλήσεων της "move_outside" και ο αριθμός των κλήσεων της "press_button".
Στο υποπρόβλημα 3, μπορείτε να λάβετε μερική βαθμολογία. Έστω $m$ η μέγιστη τιμή $\frac{q}{N}$ από όλα τα αρχεία ελέγχου (test cases) σε αυτό το υποπρόβλημα (subtask). Η βαθμολογία σας για αυτό το υποπρόβλημα υπολογίζεται σύμφωνα με τον ακόλουθο πίνακα:
Συνθήκη | Βαθμοί
:-----------------:|:----------------------------
$20 \lt m$ | $0$ (αναφέρεται ως ""Output isn't correct" στο CMS)
$6 \lt m \le 20$ | $\frac{225}{m - 2}$
$3 \lt m \le 6$ | $81 - \frac{2}{3} m^2$
$m \le 3$ | $75 $
## Υπόδειγμα βαθμολογητή
Έστω $T$ ένας πίνακας $N$ ακεραίων όπου ο $T[i]$ είναι ο τύπος του εντόμου $i$.
Ο βαθμολογητής διαβάζει την είσοδο στην ακόλουθη μορφή:
* γραμμή $1$ : $N$
* γραμμή $2$ : $T[0] \; T[1] \; \ldots \; T[N - 1]$
Εάν ο βαθμολογητής εντοπίσει protocol violation, η έξοδος του βαθμολογητή είναι `Protocol Violation: `, όπου `` είναι ένα από τα ακόλουθα:
* `invalid parameter` : σε μια κλήση προς την "move_inside" ή την "move_outside", η τιμή του $i$ δεν είναι μεταξύ του $0$ και του $N - 1$ συμπεριλαμβανομένων.
* `too many calls` : ο αριθμός των κλήσεων προς **οποιαδήποτε** εκ των "move_inside", "move_outside" ή "press_button" υπερβαίνει τις $40\;000$.
Διαφορετικά, η έξοδος του βαθμολογητή έχει την ακόλουθη μορφή:
* γραμμή $1$ : η τιμή που επιστρέφει η "min_cardinality".
* γραμμή $2$ : $q$