כדי לחסוך כסף לתא חדש באסם שלה, הפרה Bessie החלה להופיע בקרקס המקומי ולהפגין את חוש שיווי המשקל המרשים שלה, כשהיא הולכת בזהירות הלוך ושוב על קורת שיווי משקל מוגבהת!

סכום הכסף ש־Bessie מרוויחה בהופעה תלוי במקום שבו היא מצליחה בסופו של דבר לקפוץ מהקורה. המקומות על הקורה מסומנים ב־$0, 1, \ldots, N+1$ משמאל לימין. אם Bessie מגיעה אי פעם ל־$0$ או ל־$N+1$, היא נופלת מאחד מקצות הקורה ולמרבה הצער אינה מקבלת תשלום.

אם Bessie נמצאת במקום נתון $k$, היא יכולה לבצע אחת מהפעולות הבאות:

1. להטיל מטבע. אם מתקבל זנב, היא עוברת למקום $k-1$, ואם מתקבל ראש, היא עוברת למקום $k + 1$ (כלומר, ההסתברות לכל אחת משתי האפשרויות היא $\frac{1}{2}$).
2. לקפוץ מהקורה ולקבל תשלום של $f(k)$, כאשר $(0 \leq f(k) \leq 10^9)$.

Bessie מבינה שאולי לא תוכל להבטיח סכום תשלום מסוים, שכן תנועתה נקבעת על ידי הטלות מטבע אקראיות. עם זאת, בהתאם למקום שבו היא מתחילה, היא רוצה לקבוע מה תהיה תוחלת התשלום שלה אם תקבל סדרה מיטבית של החלטות (״מיטבית״ פירושו שההחלטות מביאות לתוחלת התשלום הגבוהה ביותר האפשרית). לדוגמה, אם האסטרטגיה שלה מניבה תשלום של $10$ בהסתברות $1/2$, של $8$ בהסתברות $1/4$, או של $0$ בהסתברות $1/4$, אז תוחלת התשלום שלה היא הממוצע המשוקלל $10(1/2) + 8(1/4) + 0(1/4) = 7$.

קלט

שורת הקלט הראשונה מכילה את $N$ ($2 \leq N \leq 10^5$). כל אחת מ־$N$ השורות הנותרות מכילה את אחד הערכים $f(1) \ldots f(N)$, לפי הסדר.

פלט

יש להדפיס $N$ שורות. בשורה $i$, יש להדפיס את תוחלת התשלום כאשר Bessie מתחילה במקום $i$ ופועלת באופן מיטבי, כפול $10^5$, מעוגלת כלפי מטה למספר השלם הקרוב ביותר.

דוגמאות

קלט 1

2
1
3

פלט 1

150000
300000

קרדיט לבעיה: Franklyn Wang ו־Spencer Compton