#define _USE_MATH_DEFINES #include //cin, cout #include //vector #include //sort,min,max,count #include //string,getline, to_string #include //abs(int) #include //swap, pair #include //deque #include //INT_MAX #include //bitset #include //sqrt, ceil. M_PI, pow, sin #include //fixed #include //setprecision #include //stringstream #include //gcd, assumlate #include //randam_device #include //numeric_limits using namespace std; constexpr long long int D_MOD = 1000000007; typedef struct { int no; int sum; bool flg; } stk; int main() { int N; cin >> N; vector V(N); for (int i = 0; i < N; i++) { cin >> V[i]; } vector best_t(N + 1, -1); vector best_f(N + 1, -1); deque Q; stk now, next; now.no = 0; now.sum = 0; now.flg = true; Q.push_back(now); while (!Q.empty()) { now = Q.front(); Q.pop_front(); if (now.flg) { if (best_t[now.no] > now.sum) { continue; } else { best_t[now.no] = now.sum; } } else { if (best_f[now.no] > now.sum) { continue; } else { best_f[now.no] = now.sum; } } if (now.no >= N) { continue; } if (now.flg) { next.sum = now.sum + V[now.no]; next.no = now.no + 1; next.flg = false; Q.push_back(next); } next.sum = now.sum; next.no = now.no + 1; next.flg = true; Q.push_back(next); } if (best_t[N] > best_f[N]) { cout << best_t[N] << endl; } else { cout << best_f[N] << endl; } return 0; }