// Mini-proyek Bagian 3: Memetik mangga -- versi selesai.
//
// Laporan (hasil di komputer penulis):
//   contoh kasus terkecil yang membuat greedy salah: n = 3, data "2 3 2"
//     greedy mengambil 3 lalu terkunci; jawaban benar 2 + 2 = 4
//     (penguji acak di bawah menemukan contoh lain: 7 4 3 8 7 0 9 ->
//      greedy 24, benar 26)
//   waktu brute untuk n = 22: sekitar 0,003 detik -- pemeriksaan bit
//     membuang sebagian besar mask sebelum dijumlahkan
//   waktu dp untuk n = 22: di bawah 0,000001 detik
//   waktu dp untuk n = 1.000.000: sekitar 0,004 detik
//   poin kalau hanya brute yang dikirim: 30 (hanya subsoal 1)
//   poin kalau hanya dp yang dikirim: 100
//
// Compile:  g++ -std=c++17 -O2 -o mangga projects/03-tiga-pendekatan/finished.cpp
// Jalankan: ./mangga < projects/03-tiga-pendekatan/contoh-masukan.txt

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int MAKS = 1000005;
long long a[MAKS];
long long dp[MAKS];

long long brute(int n) {
    long long terbaik = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (mask & (mask >> 1)) continue;          // ada dua bit bersebelahan
        long long jumlah = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) jumlah += a[i + 1];
        if (jumlah > terbaik) terbaik = jumlah;
    }
    return terbaik;
}

long long greedy(int n) {
    bool terlarang[64] = {false};
    bool sudah[64] = {false};
    long long total = 0;

    for (int putaran = 0; putaran < n; putaran++) {
        int pilih = -1;
        for (int i = 1; i <= n; i++)
            if (!terlarang[i] && !sudah[i] && (pilih == -1 || a[i] > a[pilih]))
                pilih = i;

        if (pilih == -1 || a[pilih] == 0) break;

        total += a[pilih];
        sudah[pilih] = true;
        if (pilih > 1) terlarang[pilih - 1] = true;
        if (pilih < n) terlarang[pilih + 1] = true;
    }
    return total;
}

long long dp_mangga(int n) {
    dp[0] = 0;
    dp[1] = a[1];
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1];
        if (dp[i - 2] + a[i] > dp[i]) dp[i] = dp[i - 2] + a[i];
    }
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    cout << dp_mangga(n) << "\n";

    // --- penguji: cari kasus yang membuat greedy salah ---
    srand(7);
    for (int uji = 1; uji <= 5000; uji++) {
        int m = rand() % 6 + 2;                  // m antara 2 dan 7
        for (int i = 1; i <= m; i++) a[i] = rand() % 10;

        long long hb = brute(m);
        long long hg = greedy(m);
        if (hb != hg) {
            cerr << "greedy salah pada n = " << m << ": ";
            for (int i = 1; i <= m; i++) cerr << a[i] << " ";
            cerr << "-> greedy " << hg << ", benar " << hb << "\n";
            break;
        }
    }

    // --- pengukuran waktu ---
    int besar = 22;
    for (int i = 1; i <= besar; i++) a[i] = rand() % 1000;

    clock_t t0 = clock();
    long long hb = brute(besar);
    double db = (double)(clock() - t0) / CLOCKS_PER_SEC;

    t0 = clock();
    long long hd = dp_mangga(besar);
    double dd = (double)(clock() - t0) / CLOCKS_PER_SEC;

    cerr << "n = 22 -> brute " << hb << " (" << db << " detik), "
         << "dp " << hd << " (" << dd << " detik)\n";

    int sejuta = 1000000;
    for (int i = 1; i <= sejuta; i++) a[i] = rand() % 1000000000;

    t0 = clock();
    long long hj = dp_mangga(sejuta);
    double dj = (double)(clock() - t0) / CLOCKS_PER_SEC;

    cerr << "n = 1000000 -> dp " << hj << " (" << dj << " detik)\n";
    return 0;
}