#include #include #include #include using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) int main(){ int N; cin >> N; vector V(N); deque d; rep(i,N){ cin >> V[i]; } // 深さ優先探索で解く // sum: ix番目までの選んだ寿司の美味しさの和を保存しておく // はじめに0番目を選んだパターンと1番目を選んだパターンの2通り考える vector sum(N); // 0番目を選んだパターン d.push_back(0); sum[0]=V[0]; while(d.size()!=0){ int ix; ix = d.back(); d.pop_back(); if(ix+2>N-1){ continue; }else if(ix+3>N-1){ sum[ix+2]=max(sum[ix+2],sum[ix]+V[ix+2]); d.push_back(ix+2); }else{ sum[ix+2]=max(sum[ix+2],sum[ix]+V[ix+2]); d.push_back(ix+2); sum[ix+3]=max(sum[ix+3],sum[ix]+V[ix+3]); d.push_back(ix+3); } } d.push_back(1); sum[1]=V[1]; while(d.size()!=0){ int ix; ix = d.back(); d.pop_back(); if(ix+2>N-1){ continue; }else if(ix+3>N-1){ sum[ix+2]=max(sum[ix+2],sum[ix]+V[ix+2]); d.push_back(ix+2); }else{ sum[ix+2]=max(sum[ix+2],sum[ix]+V[ix+2]); d.push_back(ix+2); sum[ix+3]=max(sum[ix+3],sum[ix]+V[ix+3]); d.push_back(ix+3); } } sort(sum.begin(),sum.end(),greater()); cout << sum[0] << endl; }