#include <bits/stdc++.h> using namespace std; const int N = 2002; long long dp[N][N]; long long a[N]; int main(){ ios_base::sync_with_stdio(false); int n; cin>>n; memset(dp,-1,sizeof(dp)); for(int i = 1;i<=n;i++){ cin>>a[i]; dp[i][1] = max(dp[i][1],dp[i-1][1]); dp[i][1] = max(dp[i][1],a[i]); } cout<<dp[n][1]<<endl; for(int k = 2;k<=(n+1)/2;k++){ for(int i = 1;i<=n;i++){ if(dp[i-1][k]!=-1) dp[i][k] = max(dp[i][k],dp[i-1][k]); if(i-2>=0 && dp[i-2][k-1]!=-1) dp[i][k] = max(dp[i][k],dp[i-2][k-1]+a[i]); } cout<<dp[n][k]<<endl; } return 0; }