<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 {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
       vector<int> prefix_sum(n, 0);
       prefix_sum[0] = nums[0];
       for (int i = 1; i < n; i++) {
        prefix_sum[i] = prefix_sum[i - 1] + nums[i];
       }

       // List of subarray sums starting at every index
       vector<vector<int>> subarr_sum(n);
       for (int i = 0; i < n; i++) {
        subarr_sum[i] = vector<int>(n - i);
        for (int j = i; j < n; j++) {
            int temp = prefix_sum[j] - ((i==0)? 0 : prefix_sum[i - 1]);
            subarr_sum[i][j - i] = temp; 
        }
       }

       // Merge subarray sums into a non-decreasing sum vector
       vector<int> cur_index(n, 0);
       // priority queue, small value first, contains index IDs of subarr sum list
       auto cust_greater = [&subarr_sum, &cur_index](const int a, const int b) {
        return subarr_sum[a][cur_index[a]] > subarr_sum[b][cur_index[b]];
       };
       priority_queue<int, vector<int>, decltype(cust_greater)> pQ(cust_greater);
       for (int i = 0; i < n; i++) pQ.push(i);

       // start merging, taking min from pQ
       vector<int> res(n * (n + 1) / 2, 0);
       int cur_res = 0;
       int list_id = 0;
       while (!pQ.empty()) {
        list_id = pQ.top();
        res[cur_res] = subarr_sum[list_id][cur_index[list_id]];
        pQ.pop();
        cur_index[list_id]++;
        if (cur_index[list_id] < subarr_sum[list_id].size()) {
            pQ.push(list_id);
        }
        cur_res++;
       }

    //    copy(res.begin(), res.end(), ostream_iterator<int>(cout, ", "));
       uint mod = pow(10, 9) + 7;
       int sum_res = reduce(res.begin() + left - 1, res.begin() + right, 0,
        [&mod](const int& a, const int& b){ return ((a % mod) + (b % mod)) % mod; });

       return sum_res;
    }
};
28525