Умный Бобер из ABBYY начал разработку новой развивающей игры для детей. Правила игры достаточно просты и описаны ниже.

Игровое поле представляет собой последовательность из n целых неотрицательных чисел a_i, пронумерованных от 1 до n. Цель игры — сделать числа a₁, a₂, ..., a_k (то есть некоторый префикс последовательности) равными нулю для некоторого фиксированного k (k < n), причем требуется сделать это за минимальное количество ходов.

Один ход заключается в выборе целого числа i (1 ≤ i ≤ n) такого, что a_i > 0, и целого числа t (t ≥ 0) такого, что i + 2^t ≤ n. После выбора чисел i и t значение a_i уменьшается на 1, а значение a_i + 2^t увеличивается на 1. Например, пусть n = 4 и a = (1, 0, 1, 2), тогда можно сделать ход i = 3, t = 0 и получить a = (1, 0, 0, 3) или сделать ход i = 1, t = 1 и получить a = (0, 0, 2, 2) (возможен также ещё один ход i = 1, t = 0).

Вам дано целое число n и изначальная последовательность a_i. Требуется для всевозможных k (1 ≤ k < n) посчитать минимальное количество ходов, которое требуется сделать, чтобы обнулить первые k элементов изначальной последовательности.