#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;

// 演算法 / Algorithm:
// 固定 l 時 v(l,r)=max-min 隨 r 增大不減；每個 l 形成一條由大到小的鏈。
// For fixed l, v(l,r) is non-decreasing in r; each l forms a descending chain.
// 最大堆合併 n 條鏈，取前 k 大；稀疏表讓 v(l,r) 查詢 O(1)。
// A max-heap merges the n chains to take the top-k; sparse tables answer v(l,r) in O(1).

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        int n = nums.size();

        // 計算需要的層數 K / how many sparse-table levels we need
        int K = 1;
        while ((1 << K) <= n) K++;            // 1<<K 是 2^K / 1<<K means 2^K

        // vector<vector<int>> 是二維陣列 / a 2D array; auto-initialised to 0
        vector<vector<int>> mx(K, vector<int>(n)), mn(K, vector<int>(n));
        for (int i = 0; i < n; i++) mx[0][i] = mn[0][i] = nums[i];  // 第 0 層 / level 0 = the elements

        for (int j = 1; j < K; j++)           // 由上一層建本層 / build level j from level j-1
            for (int i = 0; i + (1 << j) <= n; i++) {
                int half = 1 << (j - 1);      // 上一層窗長 / previous window length
                mx[j][i] = max(mx[j-1][i], mx[j-1][i + half]);  // 取兩半較大 / max of the two halves
                mn[j][i] = min(mn[j-1][i], mn[j-1][i + half]);  // 取兩半較小 / min of the two halves
            }

        // lambda：捕捉 [&] 表示以參考存取外部變數 / lambda capturing surrounding vars by reference
        auto val = [&](int l, int r) -> int {
            int j = 31 - __builtin_clz(r - l + 1);  // __builtin_clz 算前導零，得 floor(log2) / floor-log2 trick
            int span = 1 << j;
            int hi = max(mx[j][l], mx[j][r - span + 1]);  // 區間最大 / range max
            int lo = min(mn[j][l], mn[j][r - span + 1]);  // 區間最小 / range min
            return hi - lo;                               // 價值 / the value
        };

        // tuple<int,int,int> = (value, l, r)；priority_queue 預設最大堆，依第一元素排序
        // priority_queue is a max-heap by default; tuples compare by first element first
        priority_queue<tuple<int,int,int>> pq;
        for (int l = 0; l < n; l++)
            pq.emplace(val(l, n - 1), l, n - 1);  // emplace 直接就地建構元素 / construct in place

        long long ans = 0;                    // 用 long long 防溢位 / long long to avoid overflow (up to ~1e14)
        while (k--) {                          // 取最大的 k 個 / take the k largest values
            auto [v, l, r] = pq.top();         // 結構化綁定一次拆出三個值 / structured bindings unpack the tuple
            pq.pop();
            ans += v;
            if (r > l)                         // 同一條鏈還有下一個 / this chain has a smaller next value
                pq.emplace(val(l, r - 1), l, r - 1);  // 推入 v(l,r-1) / push it
        }
        return ans;
    }
};