/*
Mayoeba Yabureru
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
long long n , a [200005] , sum [200005][3] , l [200005] , r [200005];
set < pair < long long , pair < int , int > > > ss;
long long cost ( int l , int r )
{
long long ans = sum [r][ r % 2 ] - sum [ l - 1 ][ r % 2 ];
ans -= sum [ r - 1 ][ ( r - 1 ) % 2 ] - sum [l][ ( r - 1 ) % 2 ];
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
a [0] = a [ n + 1 ] = -1e15;
sum [0][0] = a [0];
for ( int i = 0 ; i <= n + 1 ; i ++ )
{
if ( 1 <= i && i <= n ) cin >> a [i];
sum [i][0] = sum [ i - 1 ][0];
sum [i][1] = sum [ i - 1 ][1];
sum [i][ i % 2 ] += a [i];
l [i] = r [i] = i;
ss . insert ( { a [i] , { i , i } } );
}
long long num = ( n + 1 ) / 2 , sum = 0;
for ( int i = 1 ; i <= num ; i ++ )
{
auto x = * -- ss . end ();
ss . erase ( -- ss . end () );
sum += x . first;
int lx = x . second . first - 1 , rx = x . second . second + 1;
//cout << ' ' << l [lx] << ' ' << lx << " " << rx << ' ' << r [rx] << ' ' << x . second . first << ' ' << x . second . second << ' ' << x . first << ' ' << sum << endl;
ss . erase ( ss . lower_bound ( { cost ( rx , r [rx] ) , { rx , r [rx] } } ) );
ss . erase ( ss . lower_bound ( { cost ( l [lx] , lx ) , { l [lx] , lx } } ) );
lx = l [lx] , rx = r [rx];
r [lx] = rx , l [rx] = lx;
ss . insert ( { cost ( lx , rx ) , { lx , rx } } );
cout << sum << endl;
}
}
/*
5
3 5 1 7 6
10
5383 5238 56 6356 64359 6235 23487 6693 3552 23443
64359
87846
111289
116672
116728
*/
