Балансувальне колода
Для того, щоб заробити гроші на нове стійло, корова Бессі почала виступати в місцевому цирку, демонструючи свої чудові здібності балансувати, ходячи вперед і назад по високо підвішеній колоді.
Кількість зароблених грошей залежить від того, де вона зістрибне з колоди. Колода має позиції, позначені 0, 1, ..., n + 1 зліва направо. Якщо Бессі досягне точки 0 або n + 1, вона впаде з колоди і не отримає грошей.
Якщо Бессі знаходиться в позиції k, вона може зробити одне з наступного:
Кинути монету. Якщо випаде "орел", вона переміщується в позицію k − 1, а якщо "решка", то в позицію k + 1 (тобто з ймовірністю 1 / 2 в обох випадках).
Зістрибнути з колоди і отримати плату f(k) (0 ≤ f(k) ≤
10^9).
Бессі зрозуміла, що не може гарантувати конкретний дохід, оскільки її рух контролюється випадковим киданням монети. Однак, базуючись на позиції, з якої вона починає, вона хоче визначити, якою буде її очікувана виплата, якщо вона прийме оптимальну послідовність рішень ("оптимальна" означає, що рішення приведуть до найбільш можливої очікуваної виплати). Наприклад, її стратегія заробити виплату 10 з ймовірністю 1 / 2, 8 з ймовірністю 1 / 4, або 0 з ймовірністю 1 / 4 приведе до того, що її очікувана виплата буде зваженим середнім значенням 10 * (1 / 2) + 8 * (1 / 4) + 0 * (1 / 4) = 7.
Вхідні дані
Перший рядок вводу містить n (2 ≤ n ≤ 10^5). Кожен з наступних n рядків містить f(1)...f(n).
Вихідні дані
Виведіть n рядків. У рядку i виведіть 10^5 помножене на очікувану оплату, якщо Бессі стартує в позиції i і буде діяти оптимально, округлену до найближчого цілого числа.