/*

Author: Haze

2024/4/21

*/

#include <bits/stdc++.h>

#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;

inline ll read() {
    ll s = 0;
    bool fl = false;
    char ch = (char) getchar();
    while (!isdigit(ch)) {
        if (ch == '-')fl = true;
        ch = (char) getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + (ch ^ 48);
        ch = (char) getchar();
    }
    return fl ? -s : s;
}

const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;
array<ll, 3> f[N], g[N];
// sum, li, ri
ll a[N], d[N];

array<ll, 3>tomax(array<ll, 3> p, array<ll, 3> q){
    if(p[0] > q[0])return p;
    if(q[0] > p[0])return q;
    if(p[2] - p[1] > q[2] - q[1])return q;
    return p;
}

void solve() {
    int n = read();
    irep(i, 1, n)a[i] = read();
    ll tmax = a[n], tmin = a[n];
    drep(i, n, 1){
        tmax = max(tmax, a[i]), tmin = min(tmin, a[i]);
        d[i] = tmax - tmin;
    }
    ll inf = 998244353;
    g[0] = {0, inf, -inf};
    f[0] = {-inf * inf, inf, -inf};
    irep(i, 1, n)g[i] = f[i] = {-inf, inf, -inf};
    cout << d[1] << '\n';
    irep(r, 1, n - 1){
        //f[i] 分成 r 段，且最倒数第二段的左端点为 i 的极差和最大值
        //f[i] : f[i - 1] (li, ri) => (li, ri) U ai
        //f[i] : g[i - 1] and {ai}
        f[0] = {-inf * inf, inf, -inf};
        ll sum = 0;
        irep(i, 1, n - 1){
            f[i] = {g[i - 1][0], a[i], a[i]};
            auto [val, l, r] = f[i - 1];
            val -= (r - l);
            l = min(l, a[i]), r = max(r, a[i]);
            val += (r - l);
            f[i] = tomax(f[i], {val, l, r});
            sum = max(sum, f[i][0] + d[i + 1]);
//            cerr << f[i][0] << ' ' << f[i][1] << ' ' << f[i][2] << endl;
        }
        cout << sum << '\n';
//        cerr << endl;
        swap(f, g);
    }
}

int main() {
    // IOS
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}