#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int minPartitionScore(vector<int>& a, int k)
{
    int n = a.size();
    vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 1e17));

    dp[n][0] = 0;

    for(int w = 1; w <= k; ++w)
    {
        stack<vector<ll>> st{};// stores (max in range, min value dp[range][w - 1], min value of max(a[i + 1 + j]) + dp[j][w - 1])
        for(int i = n - 1; i >= 0; --i)
        {
            ll mn = dp[i + 1][w - 1];
            while(!st.empty() && st.top()[0] <= a[i])
            {
                mn = min(mn, st.top()[1]);
                st.pop();
            }

            ll y = min(a[i] + mn, st.empty() ? (ll) 1e17 : st.top()[2]);// update the minimum, this is the value we need after adjustments
            st.push({a[i], mn, y});
            dp[i][w] = y;
        }
    }

    return dp[0][k];
}


signed main()
{

    vector<int> a{2, 5, 4, 3, 7, 1, 6, 8};

    cout<<minPartitionScore(a, 3)<<"\n";
}