The Smart Beaver from ABBYY began to develop a new educational game for children. The rules of the game are fairly simple and are described below.

The playing field is a sequence of n non-negative integers ai numbered from 1 to n. The goal of the game is to make numbers a1, a2, ..., ak (i.e. some prefix of the sequence) equal to zero for some fixed k (k < n), and this should be done in the smallest possible number of moves.

One move is choosing an integer i (1 ≤ i ≤ n) such that ai > 0 and an integer t (t ≥ 0) such that i + 2t ≤ n. After the values of i and t have been selected, the value of ai is decreased by 1, and the value of ai + 2t is increased by 1. For example, let n = 4 and a = (1, 0, 1, 2), then it is possible to make move i = 3, t = 0 and get a = (1, 0, 0, 3) or to make move i = 1, t = 1 and get a = (0, 0, 2, 2) (the only possible other move is i = 1, t = 0).

You are given n and the initial sequence ai. The task is to calculate the minimum number of moves needed to make the first k elements of the original sequence equal to zero for each possible k (1 ≤ k < n).

Input

The first input line contains a single integer n. The second line contains n integers ai (0 ≤ ai ≤ 104), separated by single spaces.

The input limitations for getting 20 points are: 

  * 1 ≤ n ≤ 300



The input limitations for getting 50 points are: 

  * 1 ≤ n ≤ 2000



The input limitations for getting 100 points are: 

  * 1 ≤ n ≤ 105

Output

Print exactly n - 1 lines: the k-th output line must contain the minimum number of moves needed to make the first k elements of the original sequence ai equal to zero.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams, or the %I64d specifier.

Examples

Input

4
1 0 1 2


Output

1
1
3


Input

8
1 2 3 4 5 6 7 8


Output

1
3
6
10
16
24
40
#include <bits/stdc++.h>
using namespace std;
const long long int inf = 1e9 + 7;
void solve();
void sieve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << fixed;
  cout << setprecision(10);
  long long int t = 1;
  while (t--) solve();
  return 0;
}
long long int pr[1001];
vector<long long int> prime;
void sieve() {
  pr[0] = -1;
  pr[1] = -1;
  long long int i, j;
  for (i = 2; i < 1001; i++) {
    if (pr[i] != -1) {
      pr[i] = 1;
      for (j = 2; j < 1001 / i + 1; j++) {
        if (i * j < 1001) pr[i * j] = -1;
      }
    }
  }
  for (i = 2; i < 1001; i++) {
    if (pr[i] == 1) prime.push_back(i);
  }
}
bool pal(string s) {
  string t = s;
  reverse(s.begin(), s.end());
  return (t == s);
}
long long int countdig(long long int x) {
  long long int c = 0;
  if (x == 0) return 1;
  while (x != 0) {
    c++;
    x /= 10;
  }
  return c;
}
bool isprime(long long int x) {
  bool flag = true;
  for (long long int i = 2; i <= sqrt(x) + 1; i++) {
    if (x % i == 0) {
      flag = false;
      break;
    }
  }
  if (x == 1) flag = false;
  return flag;
}
void swap(long long int& a, long long int& b) {
  long long int t = a;
  a = b;
  b = t;
}
class matrix {
 public:
  vector<vector<long long int>> v;
  long long int row;
  long long int col;
  matrix(vector<vector<long long int>> mat) {
    v.assign(mat.begin(), mat.end());
    row = mat.size();
    col = mat[0].size();
  }
  vector<vector<long long int>> I(long long int n) {
    vector<vector<long long int>> mat(n, vector<long long int>(n, 0));
    for (long long int i = 0; i < n; i++) mat[i][i] = 1;
    return mat;
  }
  matrix operator*(matrix& u) {
    long long int r = this->row;
    long long int c = u.col;
    assert(this->col == u.row);
    vector<vector<long long int>> res(r, vector<long long int>(c, 0));
    for (long long int i = 0; i < r; i++) {
      for (long long int j = 0; j < c; j++) {
        for (long long int k = 0; k < this->col; k++)
          res[i][j] += v[i][k] * u.v[k][j];
      }
    }
    return matrix(res);
  }
  matrix fastexpo(matrix m, long long int p) {
    assert(m.row == m.col);
    matrix res(I(m.row));
    while (p) {
      if (p & 1) res = res * m;
      m = m * m;
      p = p >> 1;
    }
    return res;
  }
};
bool comp(long long int a, long long int b) { return a > b; }
void gensparse() {
  long long int n = 5, i, j;
  long long int st[n][27];
  long long int arr[] = {1, 2, 3, 4, 5};
  for (i = 0; i < n; i++) st[i][0] = (arr[i]);
  for (j = 1; j < 27; j++) {
    for (i = 0; i + (1 << j) - 1 < n; i++) {
      st[i][j] = (st[i][j - 1] + st[i + (1 << (j - 1))][j - 1]);
    }
  }
  long long int l, r;
  cin >> l >> r;
  long long int ans = 0;
  for (j = 26; j >= 0; j--) {
    if ((1 << j) <= r - l + 1) {
      ans += st[l][j];
      l += (1 << j);
    }
  }
  cout << ans;
}
long long int solve(long long int l, long long int r, long long int n) {
  if (l > r) return 0;
  long long int g = (l + r) / 2;
  if (g == 0) return solve(g + 1, r, n);
  if (n >= (long long int)pow(26, g - 1) + 1 && n <= (long long int)pow(26, g))
    return g;
  else if (n > (long long int)pow(26, g))
    return solve(g + 1, r, n);
  else
    return solve(l, g - 1, n);
}
long long int n;
long long int next(long long int i) {
  long long int j = 0;
  for (j = 30; j >= 0; j--) {
    if (i + (1 << j) < n) break;
  }
  return i + (1 << j);
}
void solve() {
  long long int i;
  cin >> n;
  long long int arr[n];
  for (i = 0; i < n; i++) cin >> arr[i];
  long long int mov = 0;
  for (i = 0; i < n - 1; i++) {
    long long int j = next(i);
    arr[j] += arr[i];
    mov += arr[i];
    cout << mov << endl;
  }
}
