Untitled

int n = power.size();
    vector<long long> contributions(n, 0);
    stack<int> st;

    // Calculate Previous Greater Element (PGE)
    vector<int> left(n);
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && power[st.top()] <= power[i]) {
            st.pop();
        }
        left[i] = (st.empty()) ? -1 : st.top();
        st.push(i);
    }

    // Clear the stack to reuse it for the next greater element
    while (!st.empty()) st.pop();

    // Calculate Next Greater Element (NGE)
    vector<int> right(n);
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && power[st.top()] < power[i]) {
            st.pop();
        }
        right[i] = (st.empty()) ? n : st.top();
        st.push(i);
    }

    // Calculate the contributions for each element
    for (int i = 0; i < n; ++i) {
        long long left_count = i - left[i];
        long long right_count = right[i] - i;
        contributions[i] = left_count * right_count * power[i];
    }

    // Sort contributions in descending order to sum the top `k`
    sort(contributions.rbegin(), contributions.rend());

    // Sum the top `k` contributions
    long long result = 0;
    for (long i = 0; i < k && i < contributions.size(); ++i) {
        result = (result + contributions[i]) % MOD;
    }

    return static_cast<int>(result);
}