Absolutely Acidic

Συλλέγετε μετρήσεις του επιπέδου οξύτητας ενός πολύ μεγάλου ποταμιού, προκειμένου να προσδιορίσετε την "υγεία" του. Έχετε τοποθετήσει ~N~ αισθητήρες ~(2 \le N \le 2\;000\;000)~ μέσα στο ποτάμι και κάθε αισθητήρας δίνει μια ακέραια μέτρηση ~R\;(1 \le R \le 1000)~. Για τους σκοπούς της έρευνάς σας, θα θέλατε να γνωρίζετε τη συχνότητα κάθε μέτρησης και να βρείτε την απόλυτη διαφορά μεταξύ των δύο πιο συχνών μετρήσεων.

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

Είσοδος

Η πρώτη γραμμή της εισόδου θα είναι ο ακέραιος αριθμός ~N\;(2 \le N \le 2\;000\;000)~, ο αριθμός των αισθητήρων. Οι επόμενες ~N~ γραμμές περιέχουν η καθεμία την μέτρηση για τον εν λόγω αισθητήρα, η οποία θα είναι ένας ακέραιος αριθμός ~R\;(1 \le R \le 1000)~. Να υποθέσετε ότι θα υπάρχουν τουλάχιστον δύο διαφορετικές μετρήσεις στην είσοδο.

Έξοδος

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

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

input

5
1
1
1
4
3

output

3

input

4
10
6
1
8

output

9