#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::priority_queue<std::pair<i64, int>> q;
std::vector<i64> a(n + 2), l(n + 2), r(n + 2);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
q.emplace(a[i], i);
l[i] = i - 1;
r[i] = i + 1;
}
a[0] = a[n + 1] = -1E15;
std::vector<bool> del(n + 2);
i64 ans = 0;
for (int i = 1; i <= (n + 1) / 2; i++) {
while (del[q.top().second])
q.pop();
auto [v, j] = q.top();
q.pop();
ans += v;
std::cout << ans << "\n";
del[l[j]] = del[r[j]] = 1;
a[j] = a[l[j]] + a[r[j]] - a[j];
l[j] = l[l[j]];
r[j] = r[r[j]];
r[l[j]] = j;
l[r[j]] = j;
q.emplace(a[j], j);
}
return 0;
}
