Balanslaşdırıcı tirlər
Besi, yeni bir tövlə üçün pul toplamaq məqsədilə yerli sirkdə çıxış etməyə başladı. O, irəli və geri hərəkət edərək yüksəkdə asılmış bir taxta üzərində balans saxlamaq bacarığını nümayiş etdirir.
Qazandığı pul miqdarı, onun taxtadan harada tullanacağından asılıdır. Taxta soldan sağa doğru 0, 1, ..., n + 1 mövqeləri ilə işarələnib. Əgər Besi 0 və ya n + 1 nöqtəsinə çatsa, taxtadan düşəcək və pul qazanmayacaq.
Əgər Besi k mövqeyindədirsə, o, aşağıdakılardan birini edə bilər:
Pul atmaq. Əgər o, tərs ("qartal") görsə, k − 1 mövqeyinə gedir, əgər düz ("şah") görsə, k + 1 mövqeyinə gedir (hər iki halda ehtimal 1 / 2-dir).
Taxtadan tullanmaq və f(k) (0 ≤ f(k) ≤
10^9) məbləğini almaq.
Besi başa düşdü ki, konkret gəliri təmin edə bilmir, çünki onun hərəkəti təsadüfi pul atışı ilə idarə olunur. Lakin, başladığı mövqeyə əsasən, o, optimal qərar ardıcıllığını (yəni, qərarlar ən yüksək mümkün gözlənilən ödənişə gətirib çıxaracaq) qəbul edərsə, onun gözlənilən ödənişinin nə olacağını müəyyən etmək istəyir. Məsələn, onun strategiyası 1 / 2 ehtimalla 10, 1 / 4 ehtimalla 8 və 1 / 4 ehtimalla 0 ödənişini qazanmaqdırsa, onun gözlənilən ödənişi 10 * (1 / 2) + 8 * (1 / 4) + 0 * (1 / 4) = 7 olacaq.
Giriş Məlumatları
Girişin ilk sətiri n (2 ≤ n ≤ 10^5) verir. Qalan n sətirin hər biri f(1)...f(n) verir.
Çıxış Məlumatları
n sətir çıxarın. i-ci sətirdə, əgər Besi i mövqeyindən başlayıb optimal oynayarsa, gözlənilən ödənişi 10^5 ilə vurulmuş və ən yaxın tam ədədə yuvarlanmış şəkildə verin.