#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 200000 + 10;
const int INF = 1e9;
int n;
int a[MAXN];
llong answer[MAXN];
struct Range
{
int l, r;
llong sumActive;
llong sumIn;
friend bool operator < (const Range &a, const Range &b)
{
return a.l < b.l || (a.l == b.l && a.r < b.r);
}
};
struct Flip
{
llong add;
int idxL;
int idxR;
friend bool operator < (const Flip &a, const Flip &b)
{
return a.add < b.add || (a.add == b.add && a.idxL < b.idxL);
}
};
std::set <Range> ranges;
std::set <Flip> addFlip;
std::set <std::pair <llong,int>> addAlone;
bool inAddAlone[MAXN];
void addFlips(Range range)
{
// std::cout << "add flips: " << range.l << ' ' <<
if (range.l > 1 && range.r < n)
{
addFlip.insert({a[range.l - 1] + a[range.r + 1] + range.sumIn - range.sumActive, range.l, range.r});
}
}
void eraseFlips(Range range)
{
if (range.l > 1 && range.r < n)
{
addFlip.erase(addFlip.find({a[range.l - 1] + a[range.r + 1] + range.sumIn - range.sumActive, range.l, range.r}));
}
}
void addRange(int l, int r, llong sumActive, llong sumIn)
{
if (l > 1)
{
if (inAddAlone[l - 1])
{
inAddAlone[l - 1] = false;
addAlone.erase(addAlone.find({a[l - 1], l - 1}));
} else
{
auto it = ranges.lower_bound({l, l, 0, 0});
assert(it != ranges.begin());
it = std::prev(it);
assert(it->r == l - 2);
eraseFlips(*it);
sumActive += it->sumActive;
sumIn += it->sumIn + a[l - 1];
l = it->l;
ranges.erase(it);
}
}
if (r < n)
{
if (inAddAlone[r + 1])
{
inAddAlone[r + 1] = false;
addAlone.erase(addAlone.find({a[r + 1], r + 1}));
} else
{
auto it = ranges.upper_bound({r, r, 0, 0});
assert(it != ranges.end());
assert(it->l == r + 2);
eraseFlips(*it);
sumActive += it->sumActive;
sumIn += it->sumIn + a[r + 1];
r = it->r;
ranges.erase(it);
}
}
Range range = {l, r, sumActive, sumIn};
addFlips(range);
ranges.insert(range);
}
void solve()
{
for (int i = 1 ; i <= n ; ++i)
{
addAlone.insert({a[i], i});
inAddAlone[i] = true;
}
int count = 0;
llong res = 0;
while (addFlip.size() || addAlone.size())
{
if (addFlip.empty() || (addAlone.size() && addAlone.rbegin()->first > addFlip.rbegin()->add))
{
auto [add, idx] = *addAlone.rbegin();
addAlone.erase(addAlone.find(*addAlone.rbegin()));
inAddAlone[idx] = false;
res += add;
addRange(idx, idx, a[idx], 0);
count++;
} else
{
auto [add, idxL, idxR] = *addFlip.rbegin();
res += add;
auto it = ranges.lower_bound({idxL, idxL - 1, 0, 0});
assert(it != ranges.end());
auto [l, r, sumActive, sumIn] = *it;
assert(l == idxL && r == idxR);
eraseFlips(*it);
ranges.erase(it);
addRange(idxL - 1, idxR + 1, sumIn + a[idxL - 1] + a[idxR + 1], sumActive);
count++;
}
answer[count] = std::max(answer[count], res);
}
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> a[i];
}
}
void print()
{
for (int i = 1 ; i <= (n + 1) / 2 ; ++i)
{
std::cout << answer[i] << '\n';
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}
