//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
namespace debug {
template <class c> struct rge { c b, e; };
template <class c> rge<c> range(c i, c j) { return rge<c>{i, j}; }
template <class c> char spk(...);
template <class c> auto spk(c *a) -> decltype(cerr << *a, 0);
struct stream {
~stream() { cerr << endl; }
template <class c>
typename enable_if<sizeof spk<c>(0) != 1, stream &>::type operator<<(c i) {
cerr << boolalpha << i;
return *this;
}
template <class c>
typename enable_if<sizeof spk<c>(0) == 1, stream &>::type operator<<(c i) {
return *this << range(begin(i), end(i));
}
template <class a, class b> stream &operator<<(pair<a, b> p) {
return *this << "(" << p.first << ", " << p.second << ")";
}
template <class c> stream &operator<<(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; it++)
*this << ", " + 2 * (it == d.b) << *it;
return *this << "]";
}
stream &_dbg(const string &s, int i, int b) { return *this; }
template <class c, class... cs>
stream &_dbg(const string &s, int i, int b, c arg, cs... args) {
if (i == (int)(s.size()))
return (*this << ": " << arg);
b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{') - (s[i] == ')') -
(s[i] == ']') - (s[i] == '}');
return (s[i] == ',' && b == 0)
? (*this << ": " << arg << " ")._dbg(s, i + 1, b, args...)
: (s[i] == ' ' ? *this : *this << s[i])
._dbg(s, i + 1, b, arg, args...);
}
};
} // namespace debug
#ifdef DEBUG
#define dout debug::stream()
#define dbg(...) ((dout << "line:" << __LINE__ << " >> ")._dbg(#__VA_ARGS__, 0, 0, __VA_ARGS__))
#else
#define dout
#define dbg(...)
#endif
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (b); i >= (a); i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define SZ(x) (int)(x).size()
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using vi = vector<int>;
const int MAXN = 200'007;
const ll INF = 1e18;
int A[MAXN], L[MAXN], R[MAXN];
ll P[2][MAXN];
set<pair<ll, pii>, greater<pair<ll, pii>>> S;
int n;
ll ans = 0;
ll sum(int l, int r) {
if (r < l) return 0;
return P[l%2][r] - P[l%2][l-1];
}
pair<ll, pii> opp(int l, int r) {
if (l == 1 || r == n) return mp(-INF, mp(0, 0));
return mp(sum(l-1, r+1) - sum(l, r), mp(l-1, r+1));
}
// [l, s], [s+2, r]
void merge(int l, int s, int r) {
dbg("merge", l, s, r);
S.erase(opp(l, s)); S.erase(opp(s+2, r));
L[s] = R[s] = L[s+2] = R[s+2] = 0;
L[r] = l; R[l] = r;
S.insert(opp(l, r));
}
void set_interval(int l, int r) {
ans += sum(l, r) - sum(l+1, r-1);
S.insert(opp(l, r));
S.erase(mp(A[r+1], mp(r+1, r+1)));
S.erase(mp(A[l-1], mp(l-1, l-1)));
if (R[l+1]) {
L[R[l+1]] = 0; R[l+1] = 0;
}
if (L[r-1]) {
R[L[r-1]] = 0; L[r-1] = 0;
}
if (l >= 3 && L[l-2]) {
int lb = L[l-2];
merge(lb, l-2, r);
l = lb;
}
if (r+2 <= n && R[r+2]) {
int rb = R[r+2];
merge(l, r, R[r+2]);
r = rb;
}
L[r] = l; R[l] = r;
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cin >> n;
rep(i, 1, n) cin >> A[i];
rep(i, 1, n) {
rep(j, 0, 1) P[j][i] = P[j][i-1];
P[i%2][i] += A[i];
}
rep(i, 1, n) S.insert(mp(A[i], mp(i, i)));
rep(j, 1, (n+1)/2) {
dbg(S);
auto [val, i] = *S.begin();
S.erase(S.begin());
dbg(val, i);
set_interval(i.st, i.nd);
cout << ans << '\n';
}
return 0;
}
