Для того, чтобы заработать денег на новое стойло, корова Беси
начала давать представление в местном цирке, демонстрируя свои
свои замечательные возможности балансировать ходя вперёд и назад
по высоко подвешенному бревну.
Количество заработанных денег зависит от того, где она спрыгнет
с бревна. Бревно имеет позиции, помеченные \(0, 1, \ldots, N+1\)
слева направо. Если Беси достигнет точки \(0\) или \(N+1\), она
упадёт с бревна и не получит деньги.
Если Беси находится в позиции \(k\), она может сделать что-то
из следующего:
1. Бросить монету. Если она увидит хвост("орёл"), она идёт в позицию
\(k-1\), а если она увидит голову("решка"), она идёт в позицию \(k + 1\)
(т.е с вероятностью \(\frac{1}{2}\) в обоих случаях).
2. Спрыгнуть с бревна и получить плату \(f(k)\) \((0 \leq f(k) \leq 10^9)\).
Беси поняла, что она не может гарантировать конкретный доход,
поскольку её движение управляется случайным выбрасыванием монеты.
Однако, основываясь на позиции, где она начинает, она хочет определить
какой будет её ожидаемая выплата, если она сделает оптимальную последовательность
решений ("оптимальную" означает, что решения приведут к наибольшей возможной
ожидаемой выплате.)
Например, её стратегия заработать выплату \(10\) с вероятностью \(1/2\),
\(8\) с вероятностью \(1/4\), или \(0\) с вероятностью \(1/4\) приведёт к тому
что её ожидаемая выплата будет взвешенной средней величиной
\(10(1/2) + 8(1/4) + 0(1/4) = 7\).
ФОРМАТ ВВОДА (файл balance.in):
Первая строка ввода содержит \(N\) (\(2 \leq N \leq 10^5\)). Каждая из
оставшихся \(N\) строк содержит \(f(1) \ldots f(N)\).
ФОРМАТ ВЫВОДА (файл balance.out):
Выведите \(N\) строк. В строке \(i\), выведите \(10^5\) умножить на ожидаемую оплату
если Беси стартует в позиции \(i\) и будет играть оптимально, округлённую до
ближайшего целого числа.
Ваш ответ: