#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1e12;

int main() {
    // freopen("ex_seq6.in", "r", stdin);
    // freopen(".out", "w", stdout);
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, k;
    // std::cin >> n >> k;
    // n = 2e5, k = 2e3;
    n = 20, k = 10;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        // std::cin >> a[i];
        a[i] = i % 7;
    }

    std::vector<i64> s(n + 1);
    std::vector<std::vector<int>> pos(n + 1, {-1});
    std::map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        s[i + 1] = s[i] + a[i];
        pos[a[i]].push_back(i);
        mp[i] = i;
    }
    mp[n] = n;
    std::vector<std::vector<std::tuple<int, int, int, int>>> mdf(n + 1);
    auto add = [&](int xl, int xr, int yl, int yr, int v) {
        // assert(0 <= xl && xl < xr && xr <= yl && yl < yr && yr <= n + 1);
        // if (v > 0)
        // std::cerr << xl << " " << xr << " " << yl << " " << yr << ": " << v << "\n";
        mdf[xr].emplace_back(xl, yl, yr, v);
    };
    for (int x = 0; x <= n; ++x) {
        pos[x].push_back(n);
        for (int i = 0; i < int(pos[x].size()) - 1; ++i) {
            int l = pos[x][i] + 1, r = pos[x][i + 1];
            auto it = std::prev(mp.upper_bound(l));
            if (it->second >= r) {
                continue;
            }
            it = mp.emplace(l, it->second).first;
            while (it->second < r) {
                add(it->first, std::next(it)->first, it->second + 1, r + 1, x);
                it = mp.erase(it);
            }
            mp[l] = r;
        }
        // for (auto [k, v] : mp) {
        //     std::cerr << "{" << k << ", " << v << "} ";
        // }
        // std::cerr << "\n";
    }

    std::vector<i64> f(n + 1);
    f[0] = 0;
    std::deque<int> q;
    i64 cost = 0;
    for (int r = 1; r <= n; ++r) {
        f[r] = std::max(f[r], f[r - 1]);
        for (auto [l, ql, qr, x] : mdf[r]) {
            if (x == 0) {
                continue;
            }
            auto eval = [&, x = x](int i) {
                return f[i] - s[i] * x;
            };
            // i64 mx = -inf;
            cost += r - l + qr - ql;
            for (int i = std::max(l, ql - k); i < r; ++i) {
                while (!q.empty() && eval(q.back()) <= eval(i)) {
                    q.pop_back();
                }
                q.push_back(i);
                // mx = std::max(mx, f[i] - s[i] * x);
            }
            for (int i = ql; i < qr; ++i) {
                while (!q.empty() && i - q.front() > k) {
                    q.pop_front();
                }
                if (q.empty()) {
                    break;
                }
                f[i] = std::max(f[i], eval(q.front()) + s[i] * x);
            }
            q.clear();
        }
    }

    std::cout << f[n] << "\n";

    std::cerr << cost << "\n";
    std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";

    return 0;
}