Josh's Double Bacon Deluxe

Καθ' οδόν προς το χώρο του διαγωνισμού, ο Τζος, ο προπονητής του και οι ~N - 2~ συμπαίκτες του, αποφασίζουν να σταματήσουν σε ένα μπεργκεράδικο που έχει ~M~ διαφορετικά είδη μπέργκερ. Αφού παρήγγειλαν τα αγαπημένα τους μπέργκερς, τα μέλη της ομάδας παρατάχθηκαν σε μια σειρά, με τον προπονητή στην πρώτη θέση και τον Τζος τελευταίο, για να παραλάβουν τα μπέργκερ τους. Δυστυχώς, ο προπονητής ξέχασε τι είχε παραγγείλει. Διαλέγει τυχαία ένα μπέργκερ και φεύγει. Τα υπόλοιπα μέλη της ομάδας, με τη σειρά, παίρνουν το αγαπημένο τους μπέργκερ, αν είναι διαθέσιμο, ή ένα τυχαίο από τα υπόλοιπα μπέργκερ, αν δεν έχουν μείνει άλλα από το αγαπημένο τους μπέργκερ. Ποια είναι η πιθανότητα ο Τζος, όντας τελευταίος στη σειρά, να φάει το αγαπημένο του μπέργκερ;

Είσοδος

Η πρώτη γραμμή θα περιέχει τον αριθμό ~N\;(3 \le N \le 1\;000\;000)~, τον συνολικό αριθμό ατόμων και μπέργκερ. Η επόμενη γραμμή θα περιέχει ~N~ αριθμούς, με τον ~i~-οστό να είναι ο ~b_{i}\;(1 \le b_{i} \le M \le 500\;000)~, που δηλώνει τον αριθμό του αγαπημένου μπέργκερ του ~i~-οστού ατόμου. Το πρώτο άτομο στη σειρά είναι ο προπονητής και το ~N~-οστό άτομο είναι ο Τζος.

Για ~4~ από τους ~15~ διαθέσιμους βαθμούς, ~N \le 100\;000~ και ~M \le 1000~.

Για επιπλέον ~5~ από τους ~15~ διαθέσιμους βαθμούς, ~M \le 5000~.

Έξοδος

Εξάγετε έναν αριθμό ~P~ , την πιθανότητα ο Τζος να φάει το αγαπημένο του μπέργκερ, ~b_{N}~. Εάν ο η σωστή απάντηση είναι ~C~, ο βαθμολογητής θα θεωρήσει τον ~P~ σωστό αν ~\left|P - C\right| < 10^{-6}~.

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

input

3
1 2 3

output

0.5

Επεξήγηση του πρώτου παραδείγματος:

Ο προπονητής επιλέγει τυχαία μεταξύ των τριών μπέργκερ. Με πιθανότητα ~1/3~, επιλέγει το αγαπημένο του μπέργκερ (μπέργκερ ~1~) και ο Τζος τρώει έτσι κι αυτός το αγαπημένο του μπέργκερ (μπέργκερ ~3~). Με πιθανότητα ~1/3~, επιλέγει το αγαπημένο μπέργκερ του Τζος και ο Τζος έτσι δεν τρώει το αγαπημένο του μπέργκερ. Με πιθανότητα ~1/3~, επιλέγει το μπιφτέκι του δεύτερου ατόμου και υπάρχει πιθανότητα ~1/2~ το δεύτερο άτομο να επιλέξει το μπέργκερ του Τζος, στερώντας από τον Τζος την ευχαρίστηση να φάει κι εκείνος το αγαπημένο του μπέργκερ.

input

7
1 2 3 1 1 2 3

output

0.57142857