Klassinen ohjelmointitehtävä on etsiä taulukosta yhtenäinen väli, jonka lukujen summa on mahdollisimman suuri. Entä jos tehtävänä onkin etsiä yhtenäinen väli, jonka lukujen keskiarvo on mahdollisimman suuri?

Syöte

Syötteen ensimmäisellä rivillä on luku n: taulukon koko.

Toisella rivillä on n kokonaislukua x_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Ohjelmasi tulee tulostaa yksi desimaaliluku: suurin yhtenäisen välin keskiarvo.

Vastaus tulkitaan oikeaksi, jos se eroaa enintään 10^{-9} oikeasta vastauksesta.

Esimerkki

Syöte:

3
2 9 1

Tuloste:

9.0

Selitys: Välit ja keskiarvot ovat seuraavat:

• väli [2], keskiarvo 2
• väli [9], keskiarvo 9
• väli [1], keskiarvo 1
• väli [2,9], keskiarvo 5.5
• väli [9,1], keskiarvo 5
• väli [2,9,1], keskiarvo 4

Tässä taulukossa suurimman keskiarvon tuottaa väli, jossa on vain luku 9.

Rajat

Kaikissa osatehtävissä pätee:

• 1 \le x_i \le 10^9

Osatehtävä 1 (12 pistettä)

• 1 \le n \le 100

Osatehtävä 2 (17 pistettä)

• 1 \le n \le 5000

Osatehtävä 3 (71 pistettä)

• 1 \le n \le 10^5