#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N = 2e5 + 5;
ll A[N];
int Point[N];
ll Value[N];
pair<int, int> Segment[N];
int Find(int u) {
if(u == Point[u])
return u;
return Point[u] = Find(Point[u]);
}
void Union(int a, int b) {
a = Find(a);
b = Find(b);
if(a == b)
return;
Point[a] = b;
Segment[b].first = min(Segment[b].first, Segment[a].first);
Segment[b].second = max(Segment[b].second, Segment[a].second);
Value[b] += Value[a];
}
bool Correct(pair<ll, int> x)
{
int u = Find(x.second);
if((Segment[u].second - Segment[u].first) % 2 == 1)
return false;
return (Value[u] == x.first);
}
void Fix(int u, int n)
{
u = Find(u);
int a = max(1, Segment[u].first - 1);
int b = min(n, Segment[u].second + 1);
Value[u] *= -1;
Union(a, u);
Union(u, b);
}
void Solve(int n)
{
priority_queue<pair<ll, int>> PQ;
for(int i = 1; i <= n; i++) {
Point[i] = i;
Segment[i] = {i, i};
Value[i] = A[i];
PQ.push({A[i], i});
}
ll sol = 0;
for(int i = 0; i < (n+1)/2; i++) {
pair<ll, int> add;
do {
add = PQ.top();
PQ.pop();
} while(!Correct(add));
sol += add.first;
Fix(add.second, n);
PQ.push({Value[Find(add.second)], Find(add.second)});
cout << sol << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> A[i];
Solve(n);
return 0;
}
