High çayı yaxınlığında istirahət#4569
Bir cütlük çay kənarında tətil keçirmək planlaşdırır. Corc yüksək yerləri sevir və çay səviyyəsindən mümkün qədər yuxarıda olan bir məkan tapmaq istəyir. Onun həyat yoldaşı Mari isə hündürlükdən qorxur və bəndin mümkün qədər aşağıda olduğu bir yeri üstün tutur. Onlar əsas bir tərəfli yolda gedərkən çaya çıxış verən döngə var. Hər döngə məlum bir hündürlüyə malik bir yerə aparır.
Corc maşını sürür, amma Mari onu çaşdıraraq növbəti döngəni qaçırmasına səbəb ola bilər — yalnız sonuncu döngə istisna olmaqla (Corc onu həmişə görür). Bütün döngələr bir-birinə bənzəyir, ona görə də döngəyə yaxınlaşanda Corc hara gedəcəyini əvvəlcədən bilmir. Əsas yol isə sonuncu döngəni keçəndən sonra başqa bir nöqtəyə — çay kənarına aparır, onun da hündürlüyü məlumdur.
Aydındır ki, Corc aşağıdakı strategiyalardan birini seçə bilər: gördüyü ilk döngədən dönmək, ikinci döngədən dönmək, üçüncü döngədən dönmək və s. və ya ümumiyyətlə dönməmək. Əgər o, seçdiyi strategiyaya uyğun sayda döngə "görmürsə" (yəni Mari onu döngələri qaçırmağa vadar edirsə), cütlük əsas yolun sonundakı nöqtəyə gedəcək.
Sizdən tələb olunur ki, Mari də optimal şəkildə hərəkət etsə, Corc-un maksimum orta hündürlük əldə etməsi üçün optimal strategiyanı müəyyənləşdirəsiniz.
Qısıtlamalar
və h_i tam ədədlərdir. 1 \le N \le 10^5, 0 \le h_i \le 1000.
Birinci sətirdə verilir. İkinci sətirdə N+1 tam ədəd h_i verilir, burada -ci strategiyanı seçdikdə çatılan məkanın hündürlüyü göstərilir (h_{N+1} — heç bir döngədən dönmədikdə çatılan yerin hündürlüyüdür).
Birinci sətirdə, Mari optimal qarşı çıxarsa, Corcun əldə edə biləcəyi maksimum orta hündürlüyü çap edin. İkinci sətirdə isə Corcun bu hündürlüyü əldə etmək üçün hər bir təmiz strategiyanı hansı ehtimalla seçməli olduğunu göstərən N+1 ədəd çap edin. Bütün qiymətlər ən azı 10^{-6} dəqiqliklə olmalıdır.
Əgər bir neçə optimal strategiya varsa, "Heç bir döngədən dönməmək" strategiyasına ən böyük ehtimal verəni seçin. Əgər hələ də bərabərlik varsa, -ci döngədə dönmək strategiyasına ən böyük ehtimal verəni seçin və s.
Nümunə 1