Range Sum of Sorted Subarray Sums
You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number, return it modulo 10^9 + 7.
Example 1
Input
nums = [1,2,3,4], n = 4, left = 1, right = 5Output
13All subarray sums sorted are [1, 2, 3, 3, 4, 5, 6, 7, 9, 10], and the sum from index 1 to 5 is 1 + 2 + 3 + 3 + 4 = 13.
Example 2
Input
nums = [1,2,3,4], n = 4, left = 3, right = 4Output
6Using the same sorted subarray sums array, the sum from index 3 to 4 is 3 + 3 = 6.
Constraints
- n == nums.length
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 100
- 1 <= left <= right <= n * (n + 1) / 2