Pianino

Η νεαρή Mirka είναι ερασιτέχνης μουσικός. Παίζει πολυ-πιάνο. Ένα πολυ-πιάνο αποτελείται από έναν άπειρο αριθμό πολυ-πλήκτρων, που συμβολίζονται με ακέραιους αριθμούς που μπορούν να ερμηνευτούν ως τον τόνο. Μια πολυσύνθεση (μια σύνθεση γραμμένη για ένα πολυ-πιάνο) μπορεί να αναπαρασταθεί με έναν πεπερασμένο πίνακα ακεραίων, όπου οι ακέραιοι αριθμοί δηλώνουν τη σειρά των πολυ-πλήκτρων που πρέπει να πατηθούν για να παίξει η πολυσύνθεση.

Η νεαρή Mirka άκουσε μια πολυσύνθεση στο πολυ-ραδιόφωνο και τώρα θέλει να την παίξει. Δυστυχώς, δεν μπορεί να ακούσει ακριβώς ποιο πλήκτρο πατήθηκε, αλλά αντίθετα μπορεί να ακούσει εάν το πατημένο πολυ-πλήκτρο ήταν υψηλότερο, χαμηλότερο ή ίσο με το πλήκτρο που παίχτηκε προηγουμένως (ένα υψηλότερο πλήκτρο συμβολίζεται με μεγαλύτερο αριθμό). Ως εκ τούτου, αποφάσισε να παίξει τη σύνθεση με τον εξής τρόπο:

• πριν παίξει, θα επιλέξει έναν μη αρνητικό ακέραιο αριθμό ~K~
• στην αρχή, θα παίξει το σωστό πολυ-πλήκτρο (ο πολυδάσκαλός της είπε ποιο πολυ-πλήκτρο αυτό είναι)
• όταν ακούσει ότι το πολυ-πλήκτρο που παίχτηκε στη πολυσύνθεση είναι υψηλότερο από το προηγούμενο πολυπλήκτρο που έπαιξε στη πολυσύνθεση, θα παίξει το πολυ-πλήκτρο που συμβολίζεται με τον ακέραιο μεγαλύτερο από το πολυ-πλήκτρο που έπαιξε προηγουμένως από τον ~K~
• αναλόγως, όταν ακούει ότι το πολυ-πλήκτρο που παίχτηκε στην πολυσύνθεση είναι χαμηλότερο από το προηγούμενο πολυ-πλήκτρο που έπαιξε στη πολυσύνθεση, θα παίξει το πολλαπλό κλειδί που συμβολίζεται με τον ακέραιο μικρότερο από το πολυ-πλήκτρο που έπαιξε προηγουμένως από τον ~K~
• όταν ακούσει ότι το πολυ-πλήκτρο που παίζεται στην πολυσύνθεση είναι ίσο με το προηγούμενο πολυ-πλήκτρο που έπαιξε στη πολυσύνθεση, θα επαναλάβει το πολυ-πλήκτρο που έπαιξε προηγουμένως

Παρατηρήστε ότι, όταν παίζει η Mirka, δεν συγκρίνει τον τόνο των πλήκτρων που έπαιξε με τον τόνο των πλήκτρων από τη σύνθεση.

Βοηθήστε τη Mirka να επιλέξει τον ακέραιο αριθμό ~K~ για να πετύχει όσο το δυνατόν περισσότερους σωστούς τόνους.

Είσοδος

Η πρώτη γραμμή ειδόσου περιέχει τον ακέραιο αριθμό ~N\;(2 \leq N \leq 10^6 )~, τον αριθμό των πολυ-πλήκτρων στην πολυσύνθεση στο πολυ-ραδιόφωνο.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ ακέραιους αριθμούς ~a_i\;(-10^9 \leq a_i \leq 10^9)~, τα πολλαπλά πλήκτρα που παίζονται στην πολυσύνθεση.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει τον μέγιστο αριθμό πολυ-πλήκτρων που μπορεί να παίξει σωστά η Mirka.
Η δεύτερη γραμμή εξόδου πρέπει να περιέχει τον μη αρνητικό αριθμό ~K~ που πρέπει να επιλέξει η Mirka για να πετύχει όσο το δυνατόν περισσότερoους σωστούς τόνους. Ο αριθμός πρέπει να είναι μικρότερος ή ίσος με ~2 \times 10^9~.

Σημείωση: Ο απαιτούμενος αριθμός δεν χρειάζεται να είναι μοναδικός, αλλά σίγουρα θα υπάρχει εντός των δεδομένων περιορισμών.

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

input

5
1 2 0 3 1

output

3
2

Επεξήγηση του 1ου παραδείγματος: Η Mirka θα παίξει τα ακόλουθα πλήκτρα, αντίστοιχα: 1, 2, 0, 3, 1. Με έντονη γραφή είναι τα πλήκτρα που έπαιξε σωστά.

input

7
2 1 -6 -2 1 6 10

output

5
4

Επεξήγηση του 2ου παραδείγματος: Η Mirka θα παίξει τα ακόλουθα πλήκτρα, αντίστοιχα: 2, -2, -6, -2, 2, 6, 10.