В Т-Поколении очень долгие занятия. За один день надо успеть разобрать тренировочный и тематический тур, прочитать лекцию с новым материалом, а если получится, то еще и провести мини-семинар. Поэтому предусмотрен перерыв, где школьники могут уйти попить кофе и пообщаться между собой.

Всего есть $$$n+2$$$ кофемашины, которые находятся в последовательно расположенных комнатах вдоль длинного коридора. Кофемашины пронумерованы числами от $$$0$$$ до $$$n+1$$$, при чем сразу после начала перерыва у $$$i$$$-й кофемашины собралось $$$a_i$$$ школьников.

Школьники слишком громко общаются между собой, а преподавателям надо сделать очень важное объявление. Поэтому они хотят собрать наибольшее количество школьников около какой-нибудь одной кофемашины. Преподавателям слишком лениво бегать по коридорам и собирать школьников, поэтому они придумали более изощренный способ ими манипулировать:

• В любой момент преподаватели могут выбрать комнату $$$i$$$ ($$$1 \le i \le n$$$) и выключить там свет;
• Если в этой комнате находилось $$$x$$$ учеников, тогда после выключения света $$$\lfloor \frac12 x \rfloor$$$ учеников отправятся в комнату $$$(i-1)$$$, а $$$\lfloor \frac12 x \rfloor$$$ других школьников отправятся в комнату $$$(i+1)$$$.
• Если $$$x$$$ было нечетным, то один школьник остается в той же комнате.
• После этого свет в комнате $$$i$$$ включается обратно.

Преподаватели еще не решили, где они будут собирать школьников, а поэтому для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ вам следует определить, какое наибольшее количество школьников можно собрать около $$$i$$$-й кофемашины.

Преподаватели могут выключать свет в любых комнатах на свое усмотрение, в любом порядке, возможно, выключая свет в одной и той же комнате несколько раз.

Обратите внимание, что значения $$$a_0$$$ и $$$a_{n+1}$$$ никак не влияют на ответ в задаче, поэтому их значения вам даны не будут.