Junior çay kənarında istirahət
Ailə cütlüyü çayın sahilində istirahət etməyə qərar verib. 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ə getmək istəyir. Onun həyat yoldaşı Meri isə əksinə, hündürlükdən qorxur və mümkün qədər aşağı olan sahildə istirahət etmək istəyir. İndi onlar çayın yanına aparan N döngəsi olan birtərəfli əsas yolda maşınla gedirlər. Bu döngələrin hər biri çaya aparır və hər iki tərəfdaş həmin yolla aparılan yerin hündürlüyünü bilir. Sükan arxasında təbii ki, Corc oturub, lakin Meri Corcu yayındıra bilər ki, o, növbəti döngəni sonuncu döngə istisna olmaqla görə bilməsin (və Corc bunu bilir). Bütün döngələr o qədər oxşardır ki, Corc növbəti döngəyə yaxınlaşarkən onun hansı yerə apardığını dəqiq bilə bilmir. Əsas yol sonuncu döngədən sonra da davam edir və sahilin hündürlüyü məlum olan çayın yanındakı yerə aparır. Aydındır ki, Corc aşağıdakı strategiyalardan birini tətbiq edə bilər: gördüyü ilk döngədə dönmək, ikinci belə döngədə dönmək, üçüncü və s., və ya ümumiyyətlə dönməmək (açıq-aydın, əgər o, həqiqətən, nəzərdə tutduğu strategiyadan daha az döngə görərsə, cütlük əsas yolun sonunda yerləşən yerə çatacaq).
Meri də optimal şəkildə hərəkət edəcəyini nəzərə alaraq, 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 ≤ 5000, 0 ≤ h_i ≤ 1000.
Giriş verilənləri
Birinci sətirdə N sayı var. İkinci sətirdə N+1 ədəd h_i yazılıb, bu ədədlər i-ci döngədən aparan yolun hündürlüyünü müəyyən edir (h_{N+1} – əsas yoldan heç bir yerə dönməsəniz aparan yerin hündürlüyü).
Çıxış verilənləri
Birinci sətirdə Merinin optimal qarşıdurması ilə Corcun çata biləcəyi maksimum orta hündürlüyü göstərin. İkinci sətirdə N+1 ədəd göstərin – Corc bu hündürlüyə çatmaq üçün hər bir təmiz strategiyanı hansı ehtimalla tətbiq etməlidir. Bütün ölçülər 10^{-6} dəqiqliyi ilə göstərilməlidir. Əgər bir neçə optimal strategiya varsa, "Heç bir yerdə dönməmək" strategiyasının seçilmə ehtimalı maksimum olanı seçmək lazımdır. Əgər belə bir neçə varsa, N-ci döngənin seçilmə ehtimalı ən böyük olanı seçmək lazımdır və s.