A1. Развивающая игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Один ход заключается в выборе целого числа i (1 ≤ i ≤ n) такого, что ai > 0, и целого числа t (t ≥ 0) такого, что i + 2t ≤ n. После выбора чисел i и t значение ai уменьшается на 1, а значение ai + 2t увеличивается на 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 и изначальная последовательность ai. Требуется для всевозможных k (1 ≤ k < n) посчитать минимальное количество ходов, которое требуется сделать, чтобы обнулить первые k элементов изначальной последовательности.

Входные данные

Первая строка входных данных содержит единственное целое число n. Вторая строка содержит n целых чисел ai (0 ≤ ai ≤ 104), разделенных единичными пробелами.

Ограничения на входные данные для получения 20 баллов:

  • 1 ≤ n ≤ 300

Ограничения на входные данные для получения 50 баллов:

  • 1 ≤ n ≤ 2000

Ограничения на входные данные для получения 100 баллов:

  • 1 ≤ n ≤ 105
Выходные данные

Выведите ровно n - 1 строку: k-ая строка выходных данных должна содержать минимальное количество ходов, которое требуется для того, чтобы обнулить первые k элементов изначальной последовательности ai.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Примеры
Входные данные
4
1 0 1 2
Выходные данные
1
1
3
Входные данные
8
1 2 3 4 5 6 7 8
Выходные данные
1
3
6
10
16
24
40