// dmoj problem: https://vjudge.net/contest/805148#problem/B
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
using namespace std;
int n, a[200001];
void join(deque<int> &a, deque<int> &b, deque<int> &out)
{
int lp = 0;
int rp = 0;
int cur = 0;
while (lp < a.size() - 1 || rp < b.size() - 1)
{
int lcand = -INT_MAX;
int rcand = -INT_MAX;
if (lp < a.size() - 1)
lcand = a[lp + 1] - a[lp];
if (rp < b.size() - 1)
rcand = b[rp + 1] - b[rp];
if (lcand > rcand)
{
++lp;
cur += lcand;
out[lp + rp] = max(out[lp + rp], cur);
}
else
{
++rp;
cur += rcand;
out[lp + rp] = max(out[lp + rp], cur);
}
}
}
deque<int> recurse(int l, int r)
{
if (l == r)
return {0, a[l]};
if (r - l + 1 == 2)
return {0, max(a[l], a[r])};
if (r - l + 1 == 3)
return {0, max({a[l], a[l + 1], a[r]}), a[l] + a[r]};
int m = (l + r) / 2;
// a b c d e
deque<int> a = recurse(l, m - 1);
deque<int> b = recurse(m + 1, r);
deque<int> out(a.size() + b.size() - 1);
join(a, b, out);
a = recurse(l, m);
b = recurse(m + 2, r);
out.resize(max(out.size(), a.size() + b.size() - 1));
join(a, b, out);
return out;
}
int32_t main()
{
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
deque<int> out = recurse(1, n);
for (int i = 1; i <= ceil((double)n / 2); i++)
cout << out[i] << "\n";
return 0;
}
