We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 0-indexed.

Return the maximum total sum of all requests among all permutations of nums.

Since the answer may be too large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
Output: 19
Explanation: One permutation of nums is [2,1,3,4,5] with the following result: 
requests[0] -&gt; nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -&gt; nums[0] + nums[1] = 2 + 1 = 3
Total sum: 8 + 3 = 11.
A permutation with a higher total sum is [3,5,4,2,1] with the following result:
requests[0] -&gt; nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -&gt; nums[0] + nums[1] = 3 + 5  = 8
Total sum: 11 + 8 = 19, which is the best that you can do.


Example 2:

Input: nums = [1,2,3,4,5,6], requests = [[0,1]]
Output: 11
Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].

Example 3:

Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
Output: 47
Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].

&nbsp;
Constraints:


	n == nums.length
	1 &lt;= n &lt;= 105
	0 &lt;= nums[i]&nbsp;&lt;= 105
	1 &lt;= requests.length &lt;=&nbsp;105
	requests[i].length == 2
	0 &lt;= starti&nbsp;&lt;= endi&nbsp;&lt;&nbsp;n


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        count = [0] * len(nums)
        for i, j in requests:
            count[i] += 1
            if j + 1 < len(count):
                count[j+1] -= 1
        cur = 0
        for i in range(len(count)):
            count[i] += cur
            cur = count[i]
        return sum(n * c for n, c in zip(sorted(nums, reverse=True), sorted(count, reverse=True))) % (10 ** 9 + 7)
class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        int[] pref = new int[n];
        for(int i=0;i<requests.length;i++){
            pref[requests[i][0]]++;
            if(requests[i][1]+1<n)pref[requests[i][1]+1]--;
        }
        for(int i=1;i<n;i++){
            pref[i]+= pref[i-1];
        }
        Arrays.sort(nums);
        Arrays.sort(pref);
        long res = 0;
        for(int i=0;i<n;i++){
            res+=((long)pref[i]*nums[i]);
            res%=1000000007;
        }
        return (int)res%1000000007;
    }
}
class Solution {
public:
    int MOD = 1e9 + 7 ;
    vector<int> createPermutation(vector<int>&nums , vector<vector<int>> &requests){
        sort(begin(nums),end(nums)) ;
        
        vector<int>sweep(nums.size() + 1) ;
        for(auto &x : requests) ++sweep[x[0]] , --sweep[x[1] + 1] ;
        for(int i = 1 ; i < sweep.size() ; ++i ) sweep[i] += sweep[i-1] ;
        
        vector<int> aux(nums.size()) ;
        set<pair<int,int>> st ;
        for(int i = 0 ; i < nums.size() ; ++i ) st.insert({sweep[i],i}) ;
        
        int i = 0 ;
        while(st.size()){
            auto[freq,idx] = *begin(st) ;
            st.erase(begin(st)) ;
            aux[idx] = nums[i++] ;
        }
        return aux ;
    }
    
    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
        vector<int> aux = createPermutation(nums,requests);
        vector<int>pref ;
        for(auto &x : aux) pref.push_back(pref.empty() ? x : x + pref.back()) ;
        int ans = 0 ;
        for(auto &x : requests) ans = (ans + (pref[x[1]] - (x[0]-1 >= 0 ? pref[x[0] - 1] : 0) + MOD) % MOD) % MOD;
        return ans ;
    }
};
/**
 * @param {number[]} nums
 * @param {number[][]} requests
 * @return {number}
 */
var maxSumRangeQuery = function(nums, requests) {
    let frequency = new Array(nums.length).fill(0)
    for(let req of requests){
        for(let i=req[0];i<=req[1];i++){
            frequency[i]++
        }
    }
    nums = nums.sort((a,b)=>a-b)
    let freqArr = frequency.sort((a,b)=>b-a)
    let sum =0
    for(let freq of freqArr){
        sum += (freq * nums.pop())
    }
    const mod = (10 ** 9) + 7;
    return sum%mod
};
Maximum Sum Obtained of Any Permutation