Untitled

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
template<class T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

void File() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("errors.txt", "w", stderr);
#else

#endif
}

int main() {
    File();
    int n;
    cin >> n;
    ll MX = 0, subL = 0, curL = 0, ansL = 0, ansR = 0, subR = 0, curR = 0, ans = 0;
    for (ll i = 0, x; i < n; ++i) {
        cin >> x;
        // getMX element form left and swap it with minimum element in cur segment
        curL = max(curL + x, subL);
        ans = max(ans, curL);
        subL = max(subL + x, MX);
        MX = max(MX, x);
        // assum that current element is MX element and swap it with minimum element in max sub array in left
        ans = max(ansR + x, ans);
        curR = max(curR + x, subR);
        ansR = max(ansR, curR);
        subR = max(subR + x, 0LL);
        // print current answer
        cout << ans << " ";
    }
    return 0;
}