Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort 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.
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.
1 class Solution:
2 def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
3 ans = [nums[0]]
4 for i in range(1, n):
5 ans.append(nums[i])
6 nums[i] += nums[i-1]
7 ans.append(nums[i])
8 for j in range(i-1):
9 ans.append(nums[i] - nums[j])
10 ans.sort()
11 return sum(ans[left-1:right]) % 1000000007
