#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include /* signed integer */ typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef __int128_t i128; /* unsigned integer */ typedef uint8_t u8; typedef uint16_t u16; typedef uint32_t u32; typedef uint64_t u64; typedef __uint128_t u128; /* floating point number */ typedef float f32; typedef double f64; typedef long double f80; /* input / output */ static inline i64 in(void) { i64 x = 0; i64 f = 1; i64 c; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; } static inline u64 inu(void) { u64 x = 0; u64 c; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; } static inline void out(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } if (x >= 10) out(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void outu(u64 x) { if (x >= 10) outu(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); } static inline void nl(void) { putchar_unlocked('\n'); } static inline void sp(void) { putchar_unlocked(' '); } /* bits */ static inline u64 ctz(u64 n) { return __builtin_ctzll(n); } static inline u64 clz(u64 n) { return __builtin_clzll(n); } static inline u64 popcnt(u64 n) { return __builtin_popcountll(n); } static inline u64 _gcd_(u64 a, u64 b) { i32 shift = 0; while (a && b && a != b) { bool c = !(a & 1); bool d = !(b & 1); if (c && d) { ++shift; a >>= 1; b >>= 1; } else if (c && !d) a >>= 1; else if (!c && d) b >>= 1; else if (a >= b) a = (a - b) >> 1; else { u64 tmp = a; a = (b - a) >> 1; b = tmp; } } return !a ? b << shift : a << shift; } static inline u64 _lcm_(u64 a, u64 b) { return a / _gcd_(a, b) * b; } static inline i32 ceil_pow2_32(i32 n) { return n <= 1 ? 0 : 32 - __builtin_clz(n - 1); } static inline i64 ceil_pow2_64(i64 n) { return n <= 1 ? 0 : 64 - __builtin_clzl(n - 1); } /* xorshift */ static u64 _rng = 88172645463325252ULL; u64 next_rand(void) { _rng = _rng ^ (_rng << 7); return _rng = _rng ^ (_rng >> 9); } /* modint */ static inline u64 _inv(u64 mod) { int i; u64 u = 1; u64 v = 0; u64 x = 1ULL << 63; for (i = 0; i < 64; i++) { if (u & 1){ u = (u + mod) / 2; v = v / 2 + x; } else { u >>= 1; v >>= 1; } } return -v; } static inline u64 _r2(u64 mod) { return (u128) (i128) -1 % mod + 1; } static inline u64 _one(u64 mod) { return -1ULL % mod + 1; } static inline u64 _MR(u128 x, u64 inv, u64 mod) { i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64); return z < 0 ? z + mod : (u64)z; } static inline u64 to_montgomery_form(u64 a, u64 r2, u64 inv, u64 mod) { return _MR((u128)a * r2, inv, mod); } static inline u64 from_montgomery_form(u64 a, u64 inv, u64 mod) { return _MR((u128)a, inv, mod); } static inline u64 addmod64(u64 x, u64 y, u64 mod) { return x + y >= mod ? x + y - mod : x + y; } static inline u64 submod64(u64 x, u64 y, u64 mod) { return x >= y ? x - y : x - y + mod; } static inline u64 mulmod64(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod); } static inline u64 powmod64(u64 a, u64 n, u64 r2, u64 inv, u64 mod) { u64 res = _one(mod); u64 A = to_montgomery_form(a, r2, inv, mod); while (n > 0) { if (n & 1) res = _MR((u128)res * A, inv, mod); A = _MR((u128)A * A, inv, mod); n >>= 1; } return from_montgomery_form(res, inv, mod); } static inline u64 divmod64(u64 x, u64 y, u64 r2, u64 inv, u64 mod) { // assert(is_prime(mod)); u64 z = powmod64(y, mod - 2, r2, inv, mod); return mulmod64(x, z, r2, inv, mod); } static inline u64 is_prime(u64 n) { if (n < 2 || ((n % 6 != 1) && (n % 6 != 5))) return (n == 2) || (n == 3); u64 r2 = _r2(n); u64 inv = _inv(n); u64 s = ctz(n - 1); u64 d = (n - 1) >> s; u64 as[] = {2,325,9375,28178,450775,9780504,1795265022}; for (int i = 0; i < 7; i++) { u64 a = as[i]; if (_MR(a, inv, n) == 0) return 1; u64 res = powmod64(a, d, r2, inv, n); if (res == 1) continue; u64 ok = 1; for (u64 r = 0; r < s; r++) { if (res == n - 1) { ok = 0; break; } res = mulmod64(res, res, r2, inv, n); } if (ok) return 0; } return 1; } int dp[1010]; int max(int a, int b) { return (a > b) ? a : b; } void Main() { int i, N = in(); for (i = 0; i < N; i++) { int K = in(); dp[i + 1] = max(dp[i + 1], (i - 1 >= 0 ? dp[i - 1] : 0) + K); dp[i + 1] = max(dp[i + 1], dp[i]); } out(dp[N]); nl(); } int main() { Main(); return 0; }