#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 2e5 + 7 ;
const ll inf = 1e16 ;
int n ;
ll a[ MAXN ] ;
ll sm[ MAXN ] ;
int st[ MAXN ] , en[ MAXN ] ;
bool done[ MAXN ] ;
priority_queue < pair < ll , int > > q ;
void solve ( ) {
cin >> n ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ] ;
}
en[ 0 ] = 1 , st[ n + 1 ] = n ;
sm[ 0 ] = sm[ n + 1 ] = -inf ;
for ( int i = 1 ; i <= n ; ++ i ) {
sm[ i ] = a[ i ] ;
st[ i ] = i - 1 ;
en[ i ] = i + 1 ;
q.push ( { sm[ i ] , i } ) ;
}
ll ans = 0 ;
for ( int i = 1 ; i <= ( n + 1 ) / 2 ; ++ i ) {
while ( q.empty ( ) == false ) {
auto [ aux , wh ] = q.top ( ) ;
q.pop ( ) ;
if ( done[ wh ] == true ) { continue ; }
ans += aux ;
cout << ans << "\n" ;
sm[ wh ] = sm[ st[ wh ] ] + sm[ en[ wh ] ] - sm[ wh ] ;
done[ st[ wh ] ] = done[ en[ wh ] ] = true ;
q.push ( { sm[ wh ] , wh } ) ;
st[ wh ] = st[ st[ wh ] ] ;
en[ st[ wh ] ] = wh ;
en[ wh ] = en[ en[ wh ] ] ;
st[ en[ wh ] ] = wh ;
break ;
}
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
