High çayı yaxınlığında istirahət
Səfər cütlüyü çayın sahilində istirahət etmək qərarına gəldi. Corc yüksək yerləri sevir və çayın səviyyəsindən mümkün qədər yüksək olan sahilə çatmaq istəyir. Onun həyat yoldaşı Meri isə əksinə, hündürlükdən qorxur və sahilin mümkün qədər aşağı olduğu yerdə istirahət etmək istəyir. İndi onlar çayın yanına aparan N dönmə nöqtəsi olan tək istiqamətli əsas yolla maşınla gedirlər. Bu dönmə nöqtələrinin hər biri çaya aparır və hər iki tərəf yolla gedən yerin hündürlüyünü bilir. Sükan arxasında təbii ki, Corc oturur, amma Meri Corcu yayındıra bilər ki, o, növbəti dönmə nöqtəsini sonuncu dönmə nöqtəsi istisna olmaqla görə bilməsin (və Corc bunu bilir). Bütün dönmə nöqtələri o qədər oxşardır ki, Corc yaxınlaşdıqda hansı yerə aparacağını dəqiq bilmir. Əsas yol sonuncu dönmə nöqtəsindən sonra da davam edir və çayın sahilində məlum hündürlükdə olan yerə aparır. Aydındır ki, Corc aşağıdakı strategiyalardan birini tətbiq edə bilər: gördüyü ilk dönmə nöqtəsində dönmək, ikinci belə nöqtədə dönmək, üçüncü və s., ya da heç dönməmək (əgər məlum olsa ki, əslində o, nəzərdə tutduğu strategiyadan daha az dönmə nöqtəsi görürsə, cütlük əsas yolun sonunda yerləşən yerə çatacaq).
Meri də optimal şəkildə hərəkət edəcəyi fərziyyəsi ilə Corc üçün optimal strategiyanı müəyyən etmək lazımdır.
Məhdudiyyətlər
N, h_i – tam ədədlərdir. 1 ≤ N ≤ 10^5, 0 ≤ h_i ≤ 1000.
Giriş verilənləri
Birinci sətirdə N ədədi var. İkinci sətirdə N+1 ədədi h_i yazılıb, bu ədədlər i-ci dönmə nöqtəsindən gedən yolun apardığı yerin hündürlüyünü müəyyən edir (h_{N+1} – əgər heç bir yerə dönməsə, əsas yolun apardığı yerin hündürlüyü).
Çıxış verilənləri
Birinci sətirdə Merinin optimal qarşı çıxışı ilə Corcun çata biləcəyi maksimum orta hündürlüyü göstərin. İkinci sətirdə N+1 ədəd yazın – Corcun bu hündürlüyə çatmaq üçün hər bir təmiz strategiyanı tətbiq etməli olduğu ehtimallar. Bütün ölçülər 10^{-6} dəqiqliklə verilməlidir. Əgər bir neçə optimal strategiya varsa, "Heç bir yerə dönməmək" strategiyasının seçilmə ehtimalı maksimum olanını seçmək lazımdır. Əgər belə bir neçə varsa, N-ci dönmə nöqtəsinin seçilmə ehtimalı ən böyük olanını seçmək lazımdır və s.