Leetcode 3430. Maximum and Minimum Sums of at Most Size K Subarrays

Compute the total sum of the minimum plus maximum element for every subarray of nums with length at most k. The challenge is to do this efficiently (near-linear time) for n up to 80,000 rather than enumerating all subarrays.