#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 2e5 + 7 ;
const ll inf = 1e18 ;
int n ;
ll a[ MAXN ] ;
int prv[ MAXN ] ;
ll sm[ MAXN ] ;
int st[ MAXN ] , en[ MAXN ] ;
bool done[ MAXN ] ;
priority_queue < pair < ll , int > > q ;
int get ( int x ) {
if ( prv[ x ] == -1 ) { return x ; }
int y = get ( prv[ x ] ) ;
prv[ x ] = y ;
return y ;
}
void unite ( int x , int y ) {
int k1 = get ( x ) ;
int k2 = get ( y ) ;
if ( k1 != k2 ) {
done[ k2 ] = true ;
sm[ k1 ] += sm[ k2 ] ;
prv[ k2 ] = k1 ;
st[ k1 ] = min ( st[ k1 ] , st[ k2 ] ) ;
en[ k1 ] = max ( en[ k1 ] , en[ k2 ] ) ;
}
}
void solve ( ) {
cin >> n ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ] ;
}
a[ 0 ] = a[ n + 1 ] = -inf ;
for ( int i = 0 ; i <= n + 1 ; ++ i ) {
prv[ i ] = -1 , sm[ i ] = a[ i ] ;
en[ i ] = st[ i ] = i ;
if ( 1 <= i && i <= n ) {
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[ wh ] ;
done[ get ( st[ wh ] - 1 ) ] = done[ get ( en[ wh ] + 1 ) ] = true ;
unite ( wh , st[ wh ] - 1 ) ;
unite ( wh , en[ wh ] + 1 ) ;
q.push ( { sm[ wh ] , wh } ) ;
break ;
}
}
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
