<p>You are given the array <code>nums</code> consisting of <code>n</code> 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 <code>n * (n + 1) / 2</code> numbers.</p>

<p><em>Return the sum of the numbers from index </em><code>left</code><em> to index </em><code>right</code> (<strong>indexed from 1</strong>)<em>, inclusive, in the new array. </em>Since the answer can be a huge number return it modulo <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], n = 4, left = 1, right = 5
<strong>Output:</strong> 13 
<strong>Explanation:</strong> 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. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], n = 4, left = 3, right = 4
<strong>Output:</strong> 6
<strong>Explanation:</strong> The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], n = 4, left = 1, right = 10
<strong>Output:</strong> 50
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
	<li><code>1 &lt;= left &lt;= right &lt;= n * (n + 1) / 2</code></li>
</ul>

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        # res = 0
        # sum_index_pairs = [(n, j) for j, n in enumerate(nums)]
        # heapify(sum_index_pairs)
        # for i in range(1, right + 1):
        #     [sum, index] = heappop(sum_index_pairs)
        #     if index + 1 < n:
        #         heappush(sum_index_pairs, (sum + nums[index + 1], index + 1))
        #     if left <= i:
        #         res = res + sum if res + sum < 1000000007 else res + sum - 1000000007
        # return res

        pq = []
        for i in range(n):
            heapq.heappush(pq, (nums[i], i))
        ans = 0
        mod = 1e9 + 7
        for i in range(1, right + 1):
            p = heapq.heappop(pq)
            # If the current index is greater than or equal to left, add the
            # value to the answer.
            if i >= left:
                ans = (ans + p[0]) % mod
            # If index is less than the last index, increment it and add its
            # value to the first pair value.
            if p[1] < n - 1:
                p = (p[0] + nums[p[1] + 1], p[1] + 1)
                heapq.heappush(pq, p)
        return int(ans)

        # Runtime 213 ms Beats 75.71%
        # Memory 39.36 MB Beats 57.08%
        # subarray_sums = [] 
        # for i in range(len(nums)):
        #     sum = 0
        #     for j in range(i, len(nums)):
        #         sum += nums[j]
        #         subarray_sums.append(sum)
        # subarray_sums.sort()
        # sum = 0
        # for i in range(left - 1, right):
        #     sum = (sum + subarray_sums[i]) % 1000000007
        # return sum

[1,2,3,4]
4
1
5
[1,2,3,4]
4
3
4
[1,2,3,4]
4
1
10
[5,4,6,3]
4
1
10
[5,5,5,5,5]
5
1
5
[3,4,5,6,7,8]
6
1
6
[90,91,92,93,94]
5
1
5
[1,2,3,4,5,6,7,8,9]
9
1
9
[90,90,91,91,92,93,94]
7
1
7

[5,4,6,3]
4
1
10
[5,5,5,5,5]
5
1
5
[3,4,5,6,7,8]
6
1
6
[90,91,92,93,94]
5
1
5
[1,2,3,4,5,6,7,8,9]
9
1
9
[90,90,91,91,92,93,94]
7
1
7
[92,73,84,69,50,26,39,13,57,84,82,35,31,83,34,100,40,11,48,19,58,4,50,83,58,7,81,100,99,37,66,80,99,55,60,79,73,96,67,25,21,1,35,14,50,91,33,26,63,61,34,66,52,17,78,64,35,23,89,2,27,44,34,91,91,14,85,4,56,40,42,80,93,25,43,53,100,17,83,16,32,46,98,93,61,57,23,88,46,55,56,53,47,75,14,12,72,58,17,13,2,68,90,50,84,62,31,51,82,93,13,54,8,87,38,77,22,39,36,68,16,72,86,87,44,1,19,1,12,44,97,44,58,26,32,48,86,74,60,34,70,22,58,52,2,14,1,14,43,93,27,40,70,15,65,100,39,12,14,70,79,37,95,8,32,15,88,22,57,22,22,60,34,89,22,57,91,74,4,72,49,3,16,13,40,11,81,99,49,27,33,93,50,30,60,83,77,65,72,48,24,55,82,2,76,54,78,30,37,45,66,41,61,81,98,95,60,96,92,33,45,35,100,21,24,29,60,42,83,3,48,61,80,90,37,87,32,3,14,59,94,67,24,26,50,90,78,43,71,18,5,63,53,60,57,48,2,26,73,27,9,63,17,85,12,93,67,89,86,71,52,79,36,27,11,55,3,70,62,92,96,44,95,1,26,79,38,98,99,54,58,91,66,90,37,9,5,12,45,49,83,53,49,83,90,98,82,99,30,37,63,52,71,1,81,56,82,37,87,63,20,52,87,56,51,92,99,76,93,77,39,61,71,48,39,54,75,83,99,22,45,5,55,57,57,40,9,88,30,43,30,49,4,80,44,20,24,64,9,100,13,23,78,5,30,84,23,2,84,67,87,56,87,56,23,38,51,57,40,69,5,21,62,21,14,85,15,61,94,37,94,40,39,51,5,76,35,43,98,60,9,8,98,84,92,38,29,59,82,40,71,27,49,9,55,6,6,12,48,1,38,40,8,1,5,80,6,20,77,22,61,84,11,75,18,3,96,72,18,14,10,91,9,78,100,85,15,26,13,63,56,11,15,61,92,58,65,94,22,70,14,18,48,94,55,66,17,11,81,65,5,94,71,32,13,94,49,48,68,42,72,90,74,70,51,40,31,73,89,12,20,78,52,100,47,95,37,46,65,48,3,2,1,19,33,95,88,89,27,84,18,24,15,63,95,62,86,17,36,34,18,6,23,85,45,96,42,26,81,13,65,64,19,81,33,42,25,82,15,80,86,89,32,46,52,99,14,36,100,50,72,46,5,82,43,30,51,5,97,54,69,35,100,21,34,6,96,35,93,11,43,84,54,1,100,87,35,30,84,100,91,23,33,48,68,82,15,22,64,26,73,79,76,10,53,37,89,87,6,34,1,4,78,21,43,23,52,30,75,71,26,5,83,70,97,25,59,70,85,58,76,80,43,45,47,15,99,3,54,47,24,62,30,93,88,94,82,96,93,81,50,98,77,2,86,25,79,96,64,53,97,51,21,20,87,55,49,57,95,93,83,96,28,33,9,90,21,73,1,39,96,24,13,20,33,23,51,33,67,83,54,42,69,94,55,63,60,16,33,78,41,33,33,93,37,49,78,66,3,64,83,66,65,26,55,35,94,84,98,53,93,5,3,54,72,11,36,92,4,4,64,87,50,69,45,71,61,68,57,72,96,94,91,61,75,24,76,97,4,78,46,27,40,56,9,29,13,22,78,59,81,17,64,41,57,89,20,63,33,63,44,91,68,93,29,100,6,47,66,34,51,69,84,77,13,40,17,65,18,19,9,44,25,6,4,63,61,10,74,68,7,18,81,60,73,18,73,34,11,39,46,17,60,48,6,43,14,13,80,87,15,40,85,40,75,47,24,99,1,85,97,61,52,52,82,28,12,54,35,63,56,86,64,49,19,55,27,98,55,81,99,25,35,10,18,60,42,47,38,58,44,32,21,60,17,91,44,29,64,20,13,69,76,78,57,94,41,23,12,85,41,21,35,46,85,92,15,15,49,42,98,42,40,43,98,1,25,85,84,39,82,24,22,72,21,61,31,11,92,68,34,91,14,7,49,96,12,51,60,63,85,19,91,19,8,15,20,81,16,52,78,13,37,11,74,75,13,28,96,39,52,23,68,58,90,35,98,44,81,23,83,52,34,23,21,93,11,28,82,67,99,46,87,95,59,85,12,43,67,55,39,59,8,18,45,23,64,29,30,9,17,98,57,56,13,47,97,29,16,42,18,26,31,79,71,41,85,64,44,76,82,62,65,85,35,100,38,3,80,88]
1000
637
729
[100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100]
1000
1
500500
18342