#include <bits/stdc++.h> using namespace std; using ll = long long; bool comcross(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c){ return (c.second - a.second) * (b.first - c.first) >= (c.second - b.second) * (a.first - c.first); } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); ll n;cin>>n; vector<ll> A(n); for(ll &i:A) cin>>i; vector<ll> pref(n); pref[0] = A[0]; for(ll i=1;i<n;i++){ pref[i] = max(pref[i-1], A[i]); } vector<ll> dp(n, LONG_LONG_MAX); deque<pair<ll, ll>> cht; dp[n-1] = n*pref[n-1]; cht.push_front({-pref[n-1], dp[n-1]}); for(ll i=n-2;i>=0;i--){ // cout << i << ' '; // for(auto i:cht){ // cout << i.first << ':' << i.second << ' '; // } // cout << '\n'; while(cht.size() > 1){ pair<ll, ll> l1 = cht[cht.size() - 1], l2 = cht[cht.size() - 2]; if(l2.first*(i+1) + l2.second <= l1.first*(i+1) + l1.second){ cht.pop_back(); } else break; } dp[i] = (cht.back().first*(i+1) + cht.back().second) + pref[i]*n; if(cht.size() >= 1 && cht.front().first == -pref[i]){ if(cht.front().second <= dp[i]) continue; else cht.pop_front(); } // cout << cht.size() << ' '; while(cht.size() > 1 && comcross({-pref[i], dp[i]}, cht[0], cht[1])) cht.pop_front(); cht.push_front({-pref[i], dp[i]}); } ll mn=LONG_LONG_MAX; for(ll i:dp){ cout << i << ' '; mn = min(mn, i); } cout << mn << '\n'; }