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.
 
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] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> 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] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> 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].
 
Constraints:

n == nums.length
1 <= n <= 105
0 <= nums[i] <= 105
1 <= requests.length <= 105
requests[i].length == 2
0 <= starti <= endi < n

Difficulty: interview

Starter code:

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        

Solutions:
class Solution:
  def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
    count = [0] * (len(nums) + 1)
    for start, end in requests:
      count[start] += 1
      count[end + 1] -= 1
    for i in range(1, len(nums) + 1):
      count[i] += count[i - 1]
    count.pop()

    res = 0
    for n, times in zip(sorted(nums), sorted(count)):
      res += n * times

    return res % (10 ** 9 + 7)
    


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        count_lst = [0]*(len(nums) + 1)
        for start, end in requests:
            count_lst[start] += 1
            count_lst[end + 1] -= 1
        # print(count_lst)    
        ret_lst = [0]*(len(nums) + 1)
        for i in range(len(ret_lst)):
            if i == 0 and count_lst[i] != 0:
                ret_lst[i] = count_lst[i]
                continue
            
            ret_lst[i] = ret_lst[i - 1] + count_lst[i]
        # print(ret_lst)
        ret_lst.sort(reverse = True)
        nums.sort(reverse = True)
        ret_num = 0
        
        for i in range(len(nums)):
            ret_num += ret_lst[i]*nums[i]
        return ret_num % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        lenn = len(nums)
        ranks = [0] * (lenn + 1)
        for i, j in requests:
            ranks[i]  += 1
            ranks[j+1] -= 1
        for i in range(1, lenn + 1):
            ranks[i] += ranks[i-1]
        ranks = ranks[:lenn]
        return sum(x*y for x, y in zip(sorted(ranks), sorted(nums))) % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:
        n = len(A)
        count = [0] * (n + 1)
        
        for i,j in req:
            count[i] += 1
            count[j + 1] -= 1
            
        for i in range(1,n + 1):
            count[i] += count[i - 1]
        res= 0
        
        for v,c in zip(sorted(count[:-1]),sorted(A)):
            res += v * c
        return res % (10 ** 9 + 7)

from collections import defaultdict
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        count = [0] * len(nums)
        for pair in requests:
            count[pair[0]] += 1
            if pair[1] != len(nums) - 1:
                count[pair[1] + 1] -= 1
        dct = defaultdict(int)
        curr = 0
        total = 0
        for i in range(len(nums)):
            curr += count[i]
            if not curr:
                continue
            dct[curr] += 1
            total += 1
        nums.sort()
        res = 0
        items = sorted(list(dct.items()), reverse = True)
        for key, val in items:
            for i in range(val):
                res += key * nums[-1]
                nums.pop()
        return res % (10 ** 9 + 7)
        
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        interval = defaultdict(int)
        Qs = []
        Qe = []
        for [i,j] in requests:
            heapq.heappush(Qs, i)
            heapq.heappush(Qe, j+1)
        count = 0
        for i in range(len(nums)):
            while Qs and Qs[0] <= i:
                heapq.heappop(Qs)
                count += 1
            while Qe and Qe[0] <= i:
                heapq.heappop(Qe)
                count -= 1
            interval[i] = count
        #print(interval)
        keys = sorted(interval, key = lambda x: interval[x], reverse = True)
        #print(keys)
        values = sorted(nums, reverse = True)
        finala = [0 for i in range(len(nums))]
        j = 0
        for i in keys:
            finala[i] = values[j]
            j += 1
        #print(finala)
        #print(keys)
        fsum = 0
        for i in keys:
            fsum += finala[i] * interval[i]
        return fsum % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        requests.sort(reverse = True)
        counts = []
        ends = []
        curr = 0
        for i in range(N):
            while requests and requests[-1][0] == i:
                s, e = requests.pop()
                curr += 1
                heapq.heappush(ends, e)
            counts.append(curr)
            while ends and ends[0] == i:
                heapq.heappop(ends)
                curr -= 1
                
        res = 0
        for v, c in zip(sorted(counts), sorted(nums)):
            res += v * c
        return res % (10**9+7)


from heapq import *
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = (10**9 + 7)
        nums.sort(reverse=True)
        
        j = 0
        s = 0
        cnts = []
        n = len(nums)
        count = [0] * (n + 1)
        for i, j in requests:
            count[i] += 1
            count[j + 1] -= 1
            
        for i in range(1, n + 1):
            count[i] += count[i - 1]

        count.sort(reverse=True)
        
        s = 0
        for i in range(len(nums)):
            if count[i] > 0:
                s += count[i] * nums[i]
            else:
                break

        return s % MOD


class Solution:
    def maxSumRangeQuery(self, A, req):
        n = len(A)
        count = [0] * (n + 1)
        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(A)):
            res += v * c
        return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        ans = [0]*(n+1)
        for i,j in requests:
            ans[i] += 1
            ans[j+1] -= 1
        for i in range(1,n):
            ans[i] += ans[i-1]
        ans.pop()
        result = 0
        for count, value in zip(sorted(ans),sorted(nums)):
            result += count*value
        return result % (10**9+7)
        


from collections import Counter
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        stCount = Counter([request[0] for request in requests])
        endCount = Counter([request[1] for request in requests])
        tmp = []
        for st, times in stCount.items():
            tmp.append([st, 's', times])
        for end, times in endCount.items():
            tmp.append([end, 'z', times])
        nums.sort(reverse=True)
        tmp.sort()
        
        segments = []
        
        
        times = 0
        prev = 0
        MOD = (10 ** 9) + 7
        for point in tmp:
            if point[1] == 's':
                segments.append([point[0] - prev, times])
                times += point[2]
                prev = point[0]
            if point[1] == 'z':
                segments.append([point[0] - prev + 1, times])
                times -= point[2]
                prev = point[0] + 1
        
            # prev = point[0]
        segments.sort(key=lambda element:element[1], reverse=True)
        st = 0
        ans = 0
       
        for segment, times in segments:
            for i in range(st, st + segment):
                ans += nums[i] * times
            ans %= MOD
            st = st + segment
            
        
        
            
        return ans

class Solution:
    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:
            cnt = [0] * (len(a)+1)
            for s, e in r: 
                cnt[s] += 1; cnt[e+1] -= 1                    
            cnt = list(accumulate(cnt))                        
            return sum(x*y for x, y in zip(sorted(cnt[:-1]), sorted(a))) % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        bucket = [0] * N
        for a, b in requests:
            if a < N:
                bucket[a] += 1
                if b < N - 1:
                    bucket[b+1] -= 1
        bucket = list(itertools.accumulate(bucket))
        # for i in range(1, N):
            # bucket[i] = bucket[i-1] + bucket[i]
        nums.sort()
        bucket.sort()
        return sum(x * y for x, y in zip(nums, bucket)) % (10 ** 9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        a = [0 for i in range(len(nums)+1) ]
        for i in requests :
            a[i[0]] += 1
            a[i[1]+1] -= 1

        for i in range(1,len(a)):
            a[i] = a[i] + a[i-1]
            

        a.pop(-1)
        

        nums = sorted(nums,reverse=True)

        pair = [[0,number,index] for index , number in enumerate(a)]
        pair = sorted(pair,key=lambda word: (-word[1]))

        for i in range(len(nums)):
            pair[i][0] = nums[i]
        

        maxSum = 0

        for i in pair :
            maxSum += i[0] * i[1]



        return maxSum % ((10 ** 9) + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], query: List[List[int]]) -> int:
        nums = sorted(nums)
        n = len(nums)
        freq = [0] * (n+1)
        for l, r in query:
            freq[l] += 1
            freq[r+1] -= 1
        for i in range(1, n):
            freq[i] += freq[i-1]
        freq = sorted(freq[:n])
        return sum(freq[i] * nums[i] for i in range(n)) % 1000000007

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        frequencies = [0] * len(nums)
        
        for start, end in requests:
            frequencies[start] += 1
            if end+1 < len(frequencies): frequencies[end + 1] -= 1

        for i in range(1, len(frequencies)):
            frequencies[i] = frequencies[i] + frequencies[i - 1]
        
        nums.sort(reverse=True)
        frequencies.sort(reverse=True)
        
        maxSum = 0
        for i in range(len(nums)):
            maxSum += nums[i] * frequencies[i]
            
        return maxSum % (10**9 + 7)
    
    
    
\"\"\"
def maxSumRangeQuery(self, A, req):
        n = len(A)
        count = [0] * (n + 1)
        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1
        for i in xrange(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(A)):
            res += v * c
        return res % (10**9 + 7)
\"\"\"

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        l = len(nums)
        if l == 0: return 0
        acc = [0] * (l + 1)
        for r in requests:
            acc[r[0]] += 1
            acc[r[1] + 1] -= 1
        app = [0] * (l)
        app[0] = acc[0]
        for i in range(1, l):
            app[i] = app[i - 1] + acc[i]
        app.sort()
        nums.sort()
        return sum([app[i] * nums[i] for i in range(l)]) % (10 ** 9 + 7)

from collections import deque
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        freq_arr = [0]*n
        requests.sort()
        starts = deque([request[0] for request in requests])
        requests.sort(key=lambda x: x[1])
        ends =  deque([request[1] for request in requests])
        active_intervals = 0
        for pos in range(n):
            while(starts and pos==starts[0]):
                        starts.popleft()
                        active_intervals += 1
            while(ends and pos==ends[0]+1):
                        ends.popleft()
                        active_intervals -= 1            
            freq_arr[pos] = active_intervals
        
        
        nums.sort(reverse=True)
        freq_arr.sort(reverse=True)
        answer = 0
        for n,f in zip(nums,freq_arr):
            answer += n*f
        return answer % ((10**9) + 7)
        
                
                
                
                
        



class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        '''
        requests can be converted to a frequency for each spot.
        Then the highest frequency spot should get the largest item, 
        and continue to the next largest item.
        '''
        s = sorted([a for a, _ in requests])
        e = sorted([a for _, a in requests])
\t\t
        freq = [bisect_right(s, i) - bisect_left(e, i) for i in range(len(nums))]
\t\t\t
        res = sum(f * n for f, n in zip(sorted(freq), sorted(nums)))
        return res % int(1e9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        ans = [0]*(n+1)
        for i,j in requests:
            ans[i] += 1
            ans[j+1] -= 1
        for i in range(1,n):
            ans[i] += ans[i-1]
        ans.pop()
        result = 0
        for count, value in zip(sorted(ans, reverse = True),sorted(nums, reverse = True)):
            result += count*value
        return result % (10**9+7)
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        i_count = [0] * N

        for start, end in requests:
            i_count[start] += 1

            if end + 1 < N:
                i_count[end + 1] -= 1

        for i in range(1, N):
            i_count[i] += i_count[i - 1]

        s = 0
        m = 1000000007
        i_count.sort()
        nums.sort()
        for i in range(N):
            s += i_count[i] * nums[i]
            if s > m:
                s %= m

        return s

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        prefSum = [0 for x in range(len(nums))]
        starts = sorted([x[0] for x in requests])
        ends = sorted([x[1] for x in requests])
        
        count = 0
        s = 0
        e = 0
        for i in range(len(nums)):
            while s < len(starts) and starts[s] == i:
                count += 1
                s += 1
            
            while e < len(ends) and ends[e] < i:
                count -= 1
                e += 1
            
            prefSum[i] = count
        
        prefSum.sort()
        nums.sort()
        
        res = 0
        for i in range(len(nums)):
            res += prefSum[i] * nums[i]
            
        mod = int(1e9 + 7)
        
        return res % mod

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        events = []
        for s, e in requests:
            events.append((s, 1))
            events.append((e + 1, -1))
        events.sort()
        n = len(nums)
        request_count = [0] * n
        count = 0
        i = 0
        for j in range(n):
            while i < len(events) and j == events[i][0]:
                count += events[i][1]
                i += 1
            request_count[j] = count
            
        request_count.sort()
        nums.sort()
        result = 0
        while request_count and request_count[-1] > 0:
            result += request_count.pop() * nums.pop()
        return result % 1_000_000_007

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        freq = [0] * (n + 1)
        for i, j in requests:
            freq[i] += 1
            freq[j + 1] -= 1
        for i in range(1, n + 1):
            freq[i] += freq[i - 1]
        freq.sort(reverse=True)
        nums.sort(reverse=True)
        res = 0
        for i in range(n):
            res += nums[i] * freq[i]
        return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        starts = []
        ends = []
        for x, y in requests:
            starts.append(x)
            ends.append(y)
        
        starts.sort()
        ends.sort()
        
        freqs = [bisect.bisect_right(starts, i) - bisect.bisect_left(ends, i) for i in range(len(nums))]
        freqs.sort()
        nums.sort()
        res = 0
        for i, j in zip(freqs, nums):
            res += (i * j)
        return res % (10**9 + 7)


from bisect import bisect_left, bisect_right

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        s = sorted([a for a, _ in requests])
        e = sorted([a for _, a in requests])
\t\t
        freq = [bisect_right(s, i) - bisect_left(e, i) for i in range(len(nums))]
\t\t\t
        res = sum(f * n for f, n in zip(sorted(freq), sorted(nums)))
        return res % int(1e9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        cnt = [0] * n
        for st, ed in requests:
            cnt[ed] += 1
            if st > 0: cnt[st-1] -= 1
        for i in range(n-2, -1, -1):
            cnt[i] += cnt[i+1]
                
        cnt.sort(reverse=1)
        nums.sort(reverse=1)
        ans = 0
        for c, x in zip(cnt, nums):
            if c == 0: break
            ans += c * x
        return ans % MOD

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        cnt = [0] * len(nums)
        requests = sorted(requests, key = lambda x: -x[0])
        q = []
        for idx in range(len(nums)):
            while requests and idx >= requests[-1][0]:
                s, e = requests.pop()
                heapq.heappush(q, (e, s))
            while q and idx > q[0][0]:
                heapq.heappop(q)
                
            cnt[idx] = len(q)
        
        cnt.sort()
        nums.sort()
        return sum(cnt[idx] * nums[idx] for idx in range(len(nums))) % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        heap = []#heap
        dict = defaultdict(int)
        requests.sort()
        count = 0
        start = 0
        for i in requests:
            while heap and heap[0] < i[0]:#若在新的request進來前，有舊的request結尾更早結束
                heap_pop = heapq.heappop(heap)#必須pop掉
                dict[count] += heap_pop + 1 - start#這個舊的request結尾+1減去前一個start，這是一段interval，這段interval的重疊高度為count
                start = heap_pop + 1#同時更新這個這個request的結尾+1為新的start
                count -= 1#因為舊的request pop所以count-1
            heapq.heappush(heap, i[1])#用heap存這個request的結尾
            dict[count] += i[0] - start#當前這個request的起始減掉前一個start，這是一段interval，這段interval的重疊高度為count
            start = i[0]#同時更新這個這個request的起始為新的start
            count += 1#因為是新的request進來，所以count+1
        while heap:#把最後還在heap內的request pop掉
            heap_pop = heapq.heappop(heap)
            dict[count] += heap_pop + 1 - start
            start = heap_pop + 1
            count -= 1
        nums.sort(reverse = True)
        index = 0
        res = 0
        sort_key = sorted(list(dict.keys()), reverse = True)#最後按照count的數量多寡排序，count越多，就讓他乘上越大的值
        for key in sort_key:
            res += key*sum(nums[index:index+dict[key]])#把結果乘起來
            res %= (10**9+7)
            index += dict[key]
        return res
        
        
        # nums.sort(reverse = True)#request用來記錄每個時間點的起始跟結束數量，如過起始碰到結束剛好抵消，然後再用第二個for修改每個時間點room的數量(等於當前count的數量)，最後sort，再相乘
        # print(nums)
        # request = len(nums)*[0]
        # for i in range(len(requests)):
        #     request[requests[i][0]] += 1
        #     if requests[i][1]+1 < len(nums):
        #         request[requests[i][1]+1] -= 1
        # print(request)
        # count = 0
        # for i in range(len(request)):
        #     count += request[i]
        #     request[i] = count
        # request.sort(reverse = True)
        # res = 0
        # for i in range(len(request)):
        #     res = (res + request[i]*nums[i]) % (10**9+7)
        # return res
        
                
        
        # t = len(nums)*[0]#TLE
        # for a,b in requests:
        #     for j in range(a, b+1):
        #         t[j] += 1
        # nums.sort()
        # t.sort()
        # res = 0
        # for i in range(len(nums)-1, -1, -1):
        #     if t[i] == 0:
        #         break
        #     res += nums[i]*t[i]
        #     res %= (10**9+7)
        # return res


class Solution:
    def maxSumRangeQuery(self, A, req):
        n = len(A)
        count = [0] * (n + 1)

        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1

        count = list(accumulate(count))[:-1]
        count.sort()
        A.sort()
        return sum([count[i]*A[i] for i in range(n)]) % (10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        count = [0]*(len(nums)+1)
        
        for i,j in requests:
            count[i] += 1
            count[j+1] -= 1
        
        for i in range(1,len(count)):
            count[i] += count[i-1]
        
        
        total = 0
        for a,b in zip(sorted(count[:-1]),sorted(nums)):
            total += a*b
        
        return total%(10**9+7)

from collections import defaultdict
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        arr = [0]*len(nums)
        for i,j in requests:
            arr[i]+=1
            if j+1<len(arr):
                arr[j+1]-=1
        for i in range(1, len(arr)):
            arr[i]+=arr[i-1]
            
        arr.sort()
        nums.sort()
        res = 0
        
        for i,j in zip(arr, nums):
            res+=(i*j)
            
        return res%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # s,e, 
        # at most nlogn
        cnt = [0,0]
        mod = 10**9+7
        requests.sort()
        n = len(nums)
        cnt = [0]*(n)
        for s,e in requests:
            cnt[s]+=1
            if e+1<n:
                cnt[e+1]-=1
            
        print(cnt)
        real_cnt = []
        for c in cnt:
            real_cnt += [c+(real_cnt[-1] if real_cnt else 0)]
        
        cnt = real_cnt
        cnt.sort()
        nums.sort()
        print(cnt,nums)

        res = 0
        for n,c in zip(nums,cnt):
            res+=n*c
        return res%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        nums.sort(reverse=True)
        reqs = defaultdict(int)
        for start, end in requests:
            reqs[start] += 1
            reqs[end + 1] -= 1
        counts = defaultdict(int)
        h = 0
        last = -1
        for i in sorted(reqs.keys()):
            if h > 0:
                counts[h] += max(0, i - last)
            h += reqs[i]
            last = i
        res = 0
        i = 0
        n = len(nums)
        for h, c in sorted(list(counts.items()), reverse=True):
            for j in range(c):
                if i == n:
                    break
                num = nums[i]
                res += num * h
                i += 1
            res %= MOD
            if i == n:
                break
        return res


class Solution:
    def maxSumRangeQuery(self, a: List[int], req: List[List[int]]) -> int:
        n = len(a)
        count = [0] * (n + 1)
        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for count, value in zip(sorted(count[:-1]), sorted(a)):
            res += count * value
        return res % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:    
        MOD = (10 ** 9 + 7)
                
        request_counts = [0 for i in range(len(nums))]
        for l, r in requests:
            request_counts[l] += 1
            if r + 1 < len(nums):
                request_counts[r + 1] -= 1
        for i in range(1, len(nums)):
            request_counts[i] += request_counts[i - 1]
        request_counts.sort()
        nums.sort()
        
        result = 0
        for r, n in zip(request_counts, nums):
            result = (result + r * n) % MOD
            
        return result
        
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        start = collections.defaultdict(int)
        end = collections.defaultdict(int)
        min_start = 10000
        max_end = 0
        for request in requests:
            start[request[0]] += 1
            end[request[1]] += 1
            min_start = min(min_start, request[0])
            max_end = max(max_end, request[1])
        
        cnt = 0
        cnt_dic = {}
        for num in range(min_start, max_end+1):
            if num in start:
                cnt += start[num]
            if cnt > 0:
                cnt_dic[num] = cnt
            if num in end:
                cnt -= end[num]
        
        cnt_sorted = sorted(cnt_dic.values(), key = lambda x : -x)
        num_sorted = sorted(nums, key = lambda x : -x)
        result = 0
        for i, cnt in enumerate(cnt_sorted):
            result += num_sorted[i] * cnt
        return result % 1000000007

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        len_nums = len(nums)
        frequencies = [0] * (len_nums + 1)
        for start, end in requests:
            frequencies[start] += 1
            frequencies[end + 1] -= 1
        for k in range(1, len_nums):
            frequencies[k] += frequencies[k - 1]
        frequencies.sort(reverse=True)
        nums.sort(reverse=True)
        max_sum = 0
        zipper = list(zip(nums, frequencies))
        for num, frequency in zipper:
            max_sum += num * frequency
        return max_sum % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        count = [0] * (len(nums) + 1)
        mod = 10 ** 9 + 7
                
        for r in requests:
            count[r[0]] += 1
            count[r[1]+1] -= 1
        for i in range(1, len(count)):
            count[i] += count[i-1]
                 
        res = 0
        count.sort(reverse = True)
        nums.sort(reverse = True)
        for i in range(len(count)-1): 
            res = (res + (nums[i] * count[i])) % mod
            if count[i] == 0:
                break
                
        return res


import heapq
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        mymap = collections.defaultdict(int)
        n = len(nums)
        freqs = [0]*(n+1)
        for i, j in requests:
            freqs[i] += 1         
            freqs[j+1] -= 1
            
#         MADE ... prefix Sum ... algo ... to make if proper normalize ... the number of requests
#         thru indexes..
        for i in range(1, n+1):
            freqs[i] += freqs[i-1]
        
        # THIS IS TAKING o(n^2):- .... need to reduce this ... later part is amazingly fast
#         TLE -------------------------------------------------------------------------------------------      so .. we implemented above logic ... to reduce complexity

        
        # for req in requests:
        #     for ind in range(req[0], req[1]+1):
        #         mymap[ind] += 1
        
        
        
#         freqs = sorted(mymap.values(), reverse=True)
        freqs = sorted(freqs[:-1], reverse=True)
    
    
#          CAN... DO HEAP ... also ... can do ... sorting of Array
        heap = [(-n, n) for n in nums]
        
        heapq.heapify(heap)
        
        tot = 0
        for i, freq in enumerate(freqs):
            num = heapq.heappop(heap)[1]
            tot += num*freq
            tot %= (10**9 + 7)
            
        return tot % (10**9 + 7)

class Solution:
    # https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854206/JavaC%2B%2BPython-Sweep-Line
    # https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854149/C%2B%2BJava-O(n-log-n)
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort(reverse = True)
        n = len(nums)
        counter = [0 for _ in range(n + 1)]
        for i, j in requests:
            counter[i] += 1
            counter[j + 1] -= 1
        for i in range(1, n + 1):
            counter[i] += counter[i - 1]
        counter.sort(reverse = True)
        res = 0
        for i in range(n):
            res += counter[i] * nums[i]
        return res % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, a: List[int], b: List[List[int]]) -> int:
        n = len(a)
        p = [0] * (n + 1)
        for x in b:
            p[x[0]] += 1
            p[x[1] + 1] -= 1
        pref = [0] * n
        pref[0] = p[0]
        for i in range(1, n):
            pref[i] = p[i] + pref[i - 1]
        # pref.pop()
        # print(pref)
        pref.sort(reverse=True)
        a.sort(reverse=True)
        s = 0
        for i in range(n):
            s += pref[i] * a[i]
        return s % (10**9 + 7)


mod = 10**9+7

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        arr = [0]*(n+1) # add extra element for handel n+1 case
        for i, j in requests:
            arr[i]  += 1
            arr[j+1] -= 1
        for i in range(1, n+1):
            arr[i] += arr[i-1]
        arr = arr[:n] # remove extra element
        nums.sort()
        arr.sort()
        ans = 0
        for i in range(n):
            ans += nums[i] * arr[i]
        return ans%mod

from collections import defaultdict
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        count_map = defaultdict(lambda: 0)
        
        sorted_requests_start = sorted(requests, key=lambda x: x[0])
        sorted_requests_end = sorted(requests, key=lambda x: x[1])
        max_i = len(nums)
        start_ptr = 0
        ended_ptr = 0
        
        ongoing_request_list = []
        curr_request_count = 0
        for i in range(max_i):
            while start_ptr < len(requests) and sorted_requests_start[start_ptr][0] == i:
                curr_request_count += 1
                start_ptr += 1
            while ended_ptr < len(requests) and sorted_requests_end[ended_ptr][1] < i:
                curr_request_count -= 1   
                ended_ptr += 1
            ongoing_request_list.append(curr_request_count)
        
        sorted_pairs = sorted(ongoing_request_list, key=lambda x: -x)
        sorted_nums = sorted(nums, key=lambda x: -x)
        
        return int(sum(map(lambda x, y: x*y, sorted_pairs, sorted_nums)) % (1e9+7))
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mod = 10**9 + 7
        m = len(nums)
        rank = [0] * (m + 1)
        for i, j in requests:
            rank[i] += 1
            rank[j + 1] -= 1
        
        for i in range(1, m):
            rank[i] += rank[i - 1]
        
        ans = 0
        rank = rank[:m]
        nums.sort()
        rank.sort()
        for i, count in enumerate(rank):
            ans += nums[i] * count
        
        return ans % mod


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        counter = [0] * n
        for start, end in requests:
            if start < n:
                counter[start] += 1
            if end < n - 1:
                counter[end + 1] -= 1
        occurences = sorted(list(accumulate(counter)))
        nums.sort()
        res = sum([n * o for n, o in zip(nums, occurences)])
        return res % MOD

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        n=len(nums)
        prefix=[0 for i in range(len(nums))]
        for start,end in requests:
            prefix[start]+=1
            if end!=n-1:
                prefix[end+1]-=1
        for i in range(1,len(nums)):
            prefix[i]+=prefix[i-1]
        prefix.sort()
        nums.sort()
        res=0
        mod=10**9+7
        for val,time in zip(prefix,nums):
            res+=val*time
        return res%mod
            
                
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # permutation
        # requests where requests[i] = [starti, endi]
        # ith request asks for sum of 
        from operator import add
        lenn = len(nums)
        ranks = [0] * (lenn + 1)
        for i, j in requests:
            ranks[i]  += 1
            ranks[j+1] -= 1
        for i in range(1, lenn + 1):
            ranks[i] += ranks[i-1]
        ranks = ranks[:lenn]
        return sum(x*y for x, y in zip(sorted(ranks), sorted(nums))) % (10**9 + 7)
    


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        dp = [0]*len(nums)
        
        for i in range(len(requests)):
            dp[requests[i][0]] += 1
            if requests[i][1]<len(nums)-1:
                dp[requests[i][1]+1] -= 1
        
        for i in range(1, len(dp)):
            dp[i] += dp[i-1]
        
        dp.sort(reverse=True)
        nums.sort(reverse=True)
        ans = 0
        mod = int(1e9)+7
        for i in range(len(nums)):
            ans += nums[i]*dp[i]
            ans = ans%mod
        
        return ans
        


import heapq
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        
        
        mymap = collections.defaultdict(int)
        n = len(nums)
        freqs = [0]*(n+1)
        for i, j in requests:
            freqs[i] += 1         
            freqs[j+1] -= 1
            
#         MADE ... prefix Sum ... algo ... to make if proper normalize ... the number of requests
#         thru indexes..
        for i in range(1, n+1):
            freqs[i] += freqs[i-1]
            
        
            
            
        
        # THIS IS TAKING o(n^2):- .... need to reduce this ... later part is amazingly fast
#         TLE -------------------------------------------------------------------------------------------      so .. we implemented above logic ... to reduce complexity

        
        # for req in requests:
        #     for ind in range(req[0], req[1]+1):
        #         mymap[ind] += 1
        
        
        
#         freqs = sorted(mymap.values(), reverse=True)
        freqs = sorted(freqs[:-1], reverse=True)
        heap = [(-n, n) for n in nums]
        
        heapq.heapify(heap)
        
        tot = 0
        for i, freq in enumerate(freqs):
            num = heapq.heappop(heap)[1]
            tot += num*freq
            tot %= (10**9 + 7)
            
        return tot % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        called_times = [0] * n
        a = [0] * n
        mod = 10**9 + 7
        
        for i,j in requests:
            a[j] += 1
            if i-1 >= 0:
                a[i-1] -= 1
        c = 0
        for i in range(n-1,-1,-1):
            c += a[i]
            called_times[i] = c
            
        called_times.sort(reverse = True)
        nums.sort(reverse = True)
        ans = 0
        for i in range(n):
            ans += called_times[i]*nums[i]
            ans %= mod
            if called_times[i] == 0:
                break
        return ans
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mod = 10**9+7
        n = len(nums)
        
        freq = [0]*n
        heap = []
        requests.sort()
        j = 0
        for i in range(n):
            while j<len(requests) and requests[j][0] <= i:
                heapq.heappush(heap, (requests[j][1], requests[j][0]))
                j += 1
            while heap and heap[0][0] < i:
                heapq.heappop(heap)
            freq[i] = len(heap)
        
        freq.sort(reverse = True)
        nums.sort(reverse = True)
        return sum([freq[i]*nums[i] for i in range(n)]) % mod

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        ps_start=collections.defaultdict(int)
        ps_end=collections.defaultdict(int)
        for s,e in requests:
            ps_start[s]-=1
            ps_end[e]+=1
        res=[]
        for p in ps_start:res.append([p,ps_start[p]])
        for p in ps_end:res.append([p,ps_end[p]])
        res.sort()
        
        
        freq=[0 for i in range(len(nums))]
        # print(res)
        prev,count=0,0
        for p,v in res:
            if v<0:#start
                for i in range(prev,p):
                    freq[i]+=count
                prev=p
                count-=v
            else:
                for i in range(prev,p+1):
                    freq[i]+=count
                prev=p+1
                count-=v
        freq.sort()
        ans=0
        k=0
        # print(freq)
        nums.sort()
        mod=1000000007
        for f in freq:
            ans+= (f*nums[k])%mod
            k+=1
        return ans%mod
            


class Solution:
    def maxSumRangeQuery(self, n: List[int], r: List[List[int]]) -> int:
        r.sort()
        n.sort(reverse=True)
        s = sorted([x for x, y in r])
        t = sorted([y for x, y in r])
        c = collections.Counter()
        x = 0
        si, ti = 0, 0
        for i in range(s[0], t[-1] + 1):
            while si < len(s) and s[si] == i:
                x += 1
                si += 1
            c[x] += 1
            while ti < len(t) and t[ti] == i:
                x -= 1
                ti += 1
        res = 0
        print(s, t)
        print(c.most_common())
        ni = 0
        for k in sorted(c.elements(), reverse=True):
            res += k * n[ni]
            ni += 1
            
        return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:
        n = len(A)
        count = [0] * (n + 1)
        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(A)):
            res += v * c
        return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        values = [0] * (n+1)
        for i in requests:
            values[i[0]] += 1
            values[i[1]+1] -= 1
        for i in range(1, n):
            values[i] += values[i-1]
        values.sort(reverse = True)
        nums.sort(reverse = True)
        # print(values)
        ans = 0;
        mod = int(1e9) + 7;
        for i in range(n):
            ans += (values[i] * nums[i])
            ans %= mod;
        return ans
        
        
        
#         requests.sort(key = lambda x: x[0] - x[1])
#         # print(requests)
#         sz = requests[0][1] - requests[0][0] + 1
#         nums.sort(reverse = True)
#         ans = 0
#         for i in range(sz):
#             ans += nums[i]
#             ans %= mod
#         return ans;


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        cnt = [0] * (len(nums) + 2)
        for a, b in requests:
            cnt[a] += 1
            cnt[b + 1] -= 1
        for i in range(len(nums)):
            cnt[i] += cnt[i - 1]
        cnt.sort(reverse=True)
        nums.sort(reverse=True)
        return sum(a * b for a, b in zip(cnt, nums)) % (10 ** 9 + 7)

from collections import Counter

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9+7
        c = 0
        
        sn = list(sorted(nums))
        starts, ends = Counter(), Counter()
        
        for s, e in requests:
            starts[s] += 1
            ends[e+1] += 1
            
        # print(starts)
        # print(ends)
        
        repeats = []
        ranges = 0
        for i, _ in enumerate(nums):
            ranges += starts[i] - ends[i]
            repeats.append(ranges)
        
        sr = list(sorted(repeats))
        # print(sn)
        # print(sr)
        for i, r in enumerate(repeats):
            c += sn[i] * sr[i]       
        
        return c % MOD


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        d = [0] * len(nums)
        r = [0] * len(nums)
        c = 0
        j = 0
        requests.sort()
        for i in range(len(nums)):
            d[i] += c
            c -= r[i]
            r[i] = 0
            while j < len(requests) and requests[j][0] == i:
                d[i] += 1
                if requests[j][1] > i:
                    c += 1
                    r[requests[j][1]] += 1
                j += 1
                    
        ans = 0
        for a, b in zip(sorted(nums, reverse=True), sorted(d, reverse=True)):
            if not b:
                break
            ans += a * b % 1000000007
        return ans % 1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9+7
        
        nums.sort()
        ends = sorted(requests,key=lambda x: x[1])
        starts = sorted(requests, key=lambda x: x[0])
        
        ends = [x[1] for x in ends]
        starts = [x[0] for x in starts]
        
        n = len(nums)
        counts = []
        
        #print(starts)
        #print(ends)
        for i in range(n):
            endsOnBehind = len(ends)-bisect.bisect_left(ends, i)
            startsToRight = len(starts)-bisect.bisect_right(starts, i)
            
            
            counts.append(endsOnBehind-startsToRight)
        
        #print(counts)
        counts.sort()
        
        j = n-1
        ans = 0
        
        
        for i in range(len(counts)-1, -1, -1):
            if counts[i]==0:
                break
            
            ans += counts[i]*nums[j]
            ans %= MOD
            j-=1
        
        return ans
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0 for _ in range(n)]
        h = []
        requests.sort(key = lambda x: x[0])
        start = 0
        for s,e in requests:
            while h and h[0] < s:
                for i in range(start, h[0]+1):
                    count[i] += len(h)
                start = h[0]+1
                heapq.heappop(h)
            for i in range(start, s):
                count[i] += len(h)
            start = s
            heapq.heappush(h,e)
        while h:
            for i in range(start,h[0]+1):
                count[i] += len(h)
            start = h[0]+1
            heapq.heappop(h)
        mod = 10**9+7
        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod
                
                    


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        result = 0
        nums.sort()
        n = len(nums)
        LARGE = int(1e9 + 7)
        events = []
        for re in requests:
            events.append([re[0], 1])
            events.append([re[1] + 1, -1])
        # count.sort()
        events.sort()
        # print(events)
        
        prev = -1
        result = 0
        index = 0
        count = [-1 for i in range(n + 1)]
        now = 0
        for num, change in events:
            now += change
            count[num] = now
        for i in range(n):
            if (count[i] == -1):
                if i == 0:
                    count[i] = 0
                else:
                    count[i] = count[i - 1]
        count.pop()
        count.sort()
        
        # print(count)
        return sum([count[i] * nums[i] for i in range(n)]) % LARGE

class Solution:
    def maxSumRangeQuery(self, ar: List[int], requests: List[List[int]]) -> int:
        n=len(ar)
        pref=[0 for i in range (n)]
        for i in requests:
            pref[i[0]]+=1
            if i[1]+1<n:
                pref[i[1]+1]-=1
        #print(pref)
        for i in range (1,n):
            pref[i]=pref[i-1]+pref[i]
        #print(pref)
        ar.sort(reverse=True)
        pref.sort(reverse=True)
        res=0
        mod=(10**9)+7
        for i,j in zip(ar,pref):
            res=(res+(i*j))%mod
        return res
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        pts = []
        for start, end in requests:
            pts.append((start, 1))
            pts.append((end + 1, -1)) # open bracket
        
        pts.sort(key = lambda x: (x[0], x[1]))
        
        N = len(nums)
        cnts = []
        # 2 pointers
        j = 0
        cur = 0
        for i in range(N):
            if j == len(pts):
                cnts.append(cur)
                continue
            if pts[j][0] > i:
                cnts.append(cur)
            elif pts[j][0] == i:
                while j < len(pts) and pts[j][0] == i:
                    cur += pts[j][1]
                    j += 1
                cnts.append(cur)
        cnts.sort()
        nums.sort()
        ans = 0
        MOD = 10 ** 9 + 7
        for c, n in zip(cnts, nums):
            ans += c * n
            ans %= MOD
        return ans
            

            
        
        
        
        
        
        
        
        N = len(nums)
        tree = [0] * (4 * N)
        lazy = [0] * (4 * N)
        arr = nums
        def _push_down(rt, diff):
            lazy[rt * 2 + 1] += diff
            lazy[rt * 2 + 2] += diff
        def update_range_by_one(rt, lo, hi, i, j):
            if j < lo or i > hi: return
            if lazy[rt] != 0:
                tree[rt] += (hi - lo + 1) * lazy[rt]
                if lo != hi:
                    _push_down(rt, lazy[rt])
                lazy[rt] = 0
            if lo >= i and hi <= j:
                tree[rt] += (hi - lo + 1)
                if lo != hi:
                    _push_down(rt, 1)
                return
            mid = (lo + hi) // 2
            update_range_by_one(rt * 2 + 1, lo, mid, i, j)
            update_range_by_one(rt * 2 + 2, mid + 1, hi, i, j)
            tree[rt] = tree[2 * rt + 1] + tree[2 * rt + 2]
        
        def query(rt, lo, hi, i):
            if lazy[rt] != 0:
                tree[rt] += (hi - lo + 1) * lazy[rt]
                if lo != hi:
                    _push_down(rt, lazy[rt])
                lazy[rt] = 0
            if lo == hi == i: return tree[rt]
            mid = (lo + hi) // 2
            if i <= mid: return query(rt * 2 + 1, lo, mid, i)
            else: return query(rt * 2 + 2, mid + 1, hi, i)
                
        
        MOD = 10 ** 9 + 7
        for i, j in requests:
            update_range_by_one(0, 0, N - 1, i, j)
        
        cnts = []
        for i in range(N):
            cnts.append(query(0, 0, N - 1, i))
        cnts.sort()
        nums.sort()
        
        ans = 0
        for c, n in zip(cnts, nums):
            ans += c * n
            ans %= MOD
        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        ps_start=collections.defaultdict(int)
        ps_end=collections.defaultdict(int)
        for s,e in requests:
            ps_start[s]-=1
            ps_end[e]+=1
        res=[]
        for p in ps_start:res.append([p,ps_start[p]])
        for p in ps_end:res.append([p,ps_end[p]])
        res.sort()
        
        
        freq=[[i,0] for i in range(len(nums))]
        # print(res)
        prev,count=0,0
        for p,v in res:
            if v<0:#start
                for i in range(prev,p):
                    freq[i][1]+=count
                prev=p
                count-=v
            else:
                for i in range(prev,p+1):
                    freq[i][1]+=count
                prev=p+1
                count-=v
        freq.sort(key=lambda x:x[1])
        ans=0
        k=0
        # print(freq)
        nums.sort()
        mod=1000000007
        for i,f in freq:
            ans+= (f*nums[k])%mod
            k+=1
        return ans%mod
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort(reverse=True)
        a = [0]*(len(nums)+1)
        for start, end in requests:
            a[start] += 1
            a[end+1] -= 1
        for ind, val in enumerate(a[1:], 1):
            a[ind] += a[ind-1]
        a.sort(reverse=True)
        total = 0
        for k, val in zip(a, nums):
            total += k*val
        return total%(10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0 for _ in range(n)]
        h = []
        requests.sort(key = lambda x: x[0])
        start = 0
        for s,e in requests:
            while h and h[0] < s:
                for i in range(start, h[0]+1):
                    count[i] += len(h)
                start = h[0]+1
                heapq.heappop(h)
            for i in range(start, s):
                count[i] += len(h)
            start = s
            heapq.heappush(h,e)
        while h:
            for i in range(start,h[0]+1):
                count[i] += len(h)
            start = h[0]+1
            heapq.heappop(h)  
        mod = 10**9+7
        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod
                
                    


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = (10**9 + 7)
        n = len(nums)
        count = [0]*(n+1)
        for i, j in requests:
            count[i] += 1
            count[j+1] -= 1
        for i in range(1, n+1):
            count[i] += count[i-1]
        ret = 0
        for a, b in zip(sorted(count[:-1]), sorted(nums)):
            ret += a*b
        return ret % MOD


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:

        N = len(nums)
        C = [0] * (N + 1)
        
        for s, e in requests:
            C[s] += 1
            C[e + 1] -= 1
            
        for i in range(1, N):
            C[i] += C[i - 1]
        
        C.pop()
            
        
        perm = [0] * N        
        csort = [i for i, _ in sorted([(i, c) for i, c in enumerate(C)], key=lambda x: x[1])]
        
        for i, n in zip(csort, sorted(nums)):
            perm[i] = n
            
        for i in range(1, N):
            perm[i] += perm[i - 1]
            
        result = 0
        for s, e in requests:
            if s == 0:
                result += perm[e]
            else:
                result += perm[e] - perm[s - 1]
                
        return result % (10 ** 9 + 7)
            
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        d = [0] * len(nums)
        r = defaultdict(int)
        c = 0
        j = 0
        requests.sort()
        for i in range(len(nums)):
            d[i] += c
            c -= r[i]
            r[i] = 0
            while j < len(requests) and requests[j][0] == i:
                d[i] += 1
                if requests[j][1] > i:
                    c += 1
                    r[requests[j][1]] += 1
                j += 1
                    
        ans = 0
        for a, b in zip(sorted(nums, reverse=True), sorted(d, reverse=True)):
            if not b:
                break
            ans += a * b % 1000000007
        return ans % 1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        counts = [0] * n
        
        for start, end in requests:
            counts[start] += 1
            if end < n - 1:
                counts[end + 1] -= 1
        
        cur_count = 0
        for i in range(n):
            cur_count += counts[i]
            counts[i] = cur_count
        
        nums.sort()
        counts.sort()
        res = 0
        for count, num in zip(counts, nums):
            res = (res + count * num) % mod
        
        return res
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        arr = [0]*(len(nums)+1)
        for i, j in requests:
            arr[i]  += 1
            arr[j+1] -= 1
        for i in range(1, len(nums)+1):
            arr[i] += arr[i-1]
        arr=arr[:len(nums)]
        arr.sort()
        nums.sort()
        s=0
        for i in range(len(arr)):
            s+=nums[i]*arr[i]
        return s%(10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0 for _ in range(n)]
        h = []
        requests.sort(key = lambda x: x[0])
        start = 0
        for s,e in requests:
            while h and h[0] < s:
                for i in range(start, h[0]+1):
                    count[i] += len(h)
                start = h[0]+1
                heapq.heappop(h)
            for i in range(start, s):
                count[i] += len(h)
            start = s
            heapq.heappush(h,e)
        while h:
            for i in range(start,h[0]+1):
                count[i] += len(h)
            start = h[0]+1
            heapq.heappop(h)  
        print(count)
        mod = 10**9+7
        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod
                
                    


class Solution:
    def maxSumRangeQuery(self, nums, requests) -> int:
        mod_num = 10 ** 9 + 7
        n = len(nums)
        freq_arr = [0 for _ in range(n + 1)]
        for i, j in requests:
            freq_arr[i] += 1
            freq_arr[j+1] -= 1
        for i in range(1, n + 1):
            freq_arr[i] += freq_arr[i-1]
        result = sum([num * freq % mod_num for num, freq in zip(sorted(nums), sorted(freq_arr[:n]))]) % mod_num
        return result

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        d = [0] * len(nums)
        r = defaultdict(int)
        c = 0
        requests.sort()
        j = 0
        for i in range(len(nums)):
            if j >= len(requests):
                d[i] += c
                c -= r[i]
                r[i] = 0
            elif requests[j][0] > i:
                d[i] = c
                c -= r[i]
                r[i] = 0
            else:
                d[i] += c
                c -= r[i]
                r[i] = 0
                while j < len(requests) and requests[j][0] == i:
                    d[i] += 1
                    if requests[j][1] > i:
                        c += 1
                        r[requests[j][1]] += 1
                    j += 1
        #     print(i, c, r)
        # print(requests)
        # print(d)
        ans = 0
        for a, b in zip(sorted(nums, reverse=True), sorted(d, reverse=True)):
            ans += a * b % 1000000007
        return ans % 1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        '''
        Count the frequency of each index and re-arrange
        '''
        freq = [0] * (len(nums) + 1)
        for l in requests:
            freq[l[0]] += 1
            freq[l[1]+1] -= 1
        for i in range(1, len(freq)):
            freq[i] += freq[i-1]
        ans = 0
        for x, y in zip(sorted(freq[:-1]), sorted(nums)):
            ans += x * y
        return ans % 1000000007


from collections import Counter
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        count = [0] * (len(nums)+1)
        for start, end in requests:
            count[start] += 1
            count[end+1] -= 1
        for i in range(1, len(nums)+1):
            count[i] += count[i-1]
        count = count[:-1]
        summ = 0
        for num, c in zip(sorted(nums), sorted(count)):
            summ += num *c
        return summ % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9+7
        
        nums.sort()
        ends = sorted(requests,key=lambda x: x[1])
        starts = sorted(requests, key=lambda x: x[0])
        
        ends = [x[1] for x in ends]
        starts = [x[0] for x in starts]
        
        countends = collections.Counter([r[1] for r in requests])
        countstarts = collections.Counter([r[0] for r in requests])
        
        n = len(nums)
        counts = []
        
        #print(starts)
        #print(ends)
        for i in range(n):
            endsOnBehind = len(ends)-bisect.bisect_left(ends, i)
            startsToRight = len(starts)-bisect.bisect_right(starts, i)
            
            
            counts.append(endsOnBehind-startsToRight)
        
        #print(counts)
        counts.sort()
        
        j = n-1
        ans = 0
        
        
        for i in range(len(counts)-1, -1, -1):
            if counts[i]==0:
                break
            
            ans += counts[i]*nums[j]
            ans %= MOD
            j-=1
        
        return ans
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], req: List[List[int]]) -> int:
        n = len(nums)
       
        count = [0] * (n + 1)
        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(nums)):
            res += v * c
        return res % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        requests = sorted(requests)
        repeated, dp, idx = [],[],0
        for i in range(len(nums)):
            while dp and dp[0] < i:
                heapq.heappop(dp)
            while idx < len(requests) and requests[idx][0] <= i:
                heapq.heappush(dp, requests[idx][1])
                idx += 1
            repeated.append(len(dp))
        return sum([x*y for x,y in zip(sorted(nums), sorted(repeated))])%(10**9 + 7)


class Solution:
    import heapq
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort(reverse=True)
        res=[[] for i in range(len(nums))]
        heap=[]
        for request in requests:
            res[request[0]].append(request[1])
        countNum=[0]*len(nums)
        for i in range(len(res)):
            if res[i]:
                for element in res[i]:
                    heapq.heappush(heap,element)
            countNum[i]+=len(heap)
            while heap and heap[0]==i:
                heapq.heappop(heap)
        countNum.sort(reverse=True)
        count=0
        for i in range(len(nums)):
            count+=(nums[i]*countNum[i])%(10**9+7)
        return count%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)
        
        events = []
        OPEN = -1
        CLOSE = 1
        for u, v in requests:
            events.append([u, OPEN])
            events.append([v, CLOSE])
        events.sort()
        weights = [0] * n
        
        open_events = 0
        nxt_event = 0
        
        for i in range(n):
            # open here
            while nxt_event < len(events) and events[nxt_event][0] <= i:
                if events[nxt_event][1] == OPEN:
                    open_events += 1
                else:
                    break
                nxt_event += 1
            # compute weight
            weights[i] = open_events
            # close here
            while nxt_event < len(events) and events[nxt_event][0] <= i:
                if events[nxt_event][1] == CLOSE:
                    open_events -= 1
                nxt_event += 1

        return sum([w * num for w,num in zip(sorted(weights), sorted(nums)) ]) % MOD
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        dp = [0] * (len(nums)+1)
        
        for r in requests:
            dp[r[0]] += 1
            dp[r[1]+1] -= 1
            
        counts = [0] * len(nums)
        counts[0] = dp[0]
        for i in range(len(nums)):
            counts[i] = counts[i-1] + dp[i]
            
        # print(counts)
        nums.sort()
        counts.sort()
        
        ans = 0
        for n, c in zip(nums, counts):
            ans += n*c
        
        return ans % (10**9+7)

class Solution:
    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:
        ends = []
        for s, e in r: ends.extend([(s, 1), (e+1, -1)])                    
        ends.sort(reverse=True)
        n, op = len(a), 0        
        cnt = [0] * n
        for i in range(n):               
            while ends and ends[-1][0] == i: op += ends.pop()[1]                         
            cnt[i] = op  
        return sum(x*y for x, y in zip(sorted(cnt), sorted(a))) % (10**9 + 7)

class Solution:
        def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
            n = len(nums)
            arr = [0]*(n+1) # add extra element for handel n+1 case
            for i, j in requests:
                arr[i]  += 1
                arr[j+1] -= 1
            for i in range(1, n+1):
                arr[i] += arr[i-1]
            arr = arr[:n] # remove extra element
            nums.sort()
            arr.sort()
            ans = 0
            for i in range(n):
                ans += nums[i] * arr[i]
            return(ans%(10**9+7))


from typing import List
import collections
import heapq
import itertools
import bisect


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        s = sorted([a for a, _ in requests])
        e = sorted([a for _, a in requests])
        freq = []
        for i in range(len(nums)):
            start_after = bisect.bisect_right(s, i)
            end_before = bisect.bisect_left(e, i)
            # print(start_after, end_before)
            # in_it = int(start_after == end_before and start_after < len(requests) and )
            freq.append(start_after - end_before)
        # print(freq)
        freq.sort(reverse=True)
        nums.sort(reverse=True)
        res = 0
        for i, f in enumerate(freq):
            res += int(f * nums[i] % (1e9 + 7))
        return int(res % (1e9 + 7))


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        ok=[0]*(len(nums)+1)
        for i in requests:
            ok[i[0]]+=1
            ok[i[1]+1]-=1
        ok=[0]+ok
        for i in range(1,len(ok)):
            ok[i]+=ok[i-1]
        ok=ok[1:-1]  
        ok.sort(reverse=True)
        ans=0
        nums.sort(reverse=True)
        for i in range(len(nums)):
            ans+=nums[i]*ok[i]
        return ans%1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n, MOD= len(nums), 10**9+7
        count = [0]*(n+1)
        for s, e in requests:
            count[s]+=1
            count[e+1]-=1
        for i in range(1, n):
            count[i]+=count[i-1]
        return sum(a*b for a,b in zip(sorted(count[:n]), sorted(nums)))%MOD

class Solution:
    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:
        r1 = []
        for s, e in r:            
            r1.extend([(s, 1), (e, -1)])            
        r = r1
        r.sort(reverse=True)
        op = 0
        n = len(a)
        cand = []
        cur_start = 0        
        cur_end = -1
        cnt = [0] * n
        for i in range(n):   
            cl = 0
            while r and r[-1][0] == i:
                p = r.pop()[1]                
                op +=  p == 1
                cl += p == -1
            cnt[i] = op
            op -= cl
        cnt.sort()
        a.sort()
        # print(cnt, a)
        return sum(x*y for x, y in zip(cnt, a)) % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        freqs = [0] * (len(nums) + 1)
        for s, e in requests:
            freqs[s] += 1
            freqs[e + 1] -= 1
        freqs.pop()
        f = 0
        for i, x in enumerate(freqs):
            f += x
            freqs[i] = f
        nums.sort()
        freqs.sort()
        result = 0
        for n, f in zip(nums, freqs):
            result += f * n
        return result % 1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        begin = [0] * (n+1)
        end = [0] * (n+1)
        for x,y in requests :
            begin[x] += 1
            end[y+1] += 1        
        l = []
        cnt = 0
        for i in range(n) :
            cnt += begin[i] - end[i]
            l.append(cnt)
        l.sort()
        nums.sort()
        res = 0
        for i in range(n) :
            res += l[i] * nums[i]
        return res % (10**9 + 7)
                


class Solution:
    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:
        ends = []
        for s, e in r: ends.extend([(s, 1), (e, -1)])                    
        ends.sort(reverse=True)
        n, op = len(a), 0        
        cnt = [0] * n
        for i in range(n):   
            cl = 0
            while ends and ends[-1][0] == i:
                p = ends.pop()[1]                
                op +=  p == 1
                cl += p == -1
            cnt[i] = op
            op -= cl
        cnt.sort(); a.sort()        
        return sum(x*y for x, y in zip(cnt, a)) % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        counts = [0 for _ in range(n)]
        for i, j in requests:
            counts[i] += 1
            if j + 1 < n:
                counts[j+1] -= 1
        
        for i in range(1, n):
            counts[i] += counts[i-1]
        
        nums.sort()
        counts.sort()
        
        mod = 10 ** 9 + 7
        r = 0
        
        for i in range(n):
            r += nums[i] * counts[i]
        
        return r % mod

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        arr = [0] * n
        for s, e in requests:
            arr[s] += 1
            if e < n - 1:
                arr[e + 1] -= 1
        for i in range(1, n):
            arr[i] += arr[i - 1]
        nums.sort()
        res = 0
        mod = 10**9 + 7
        for a in sorted(arr, reverse=1):
            res += a * nums.pop()
        return res % mod
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        N = len(nums)
        index_weight = collections.defaultdict(int)
        for s, e in requests:
            index_weight[s] += 1
            index_weight[e + 1] -= 1
        
        for i in range(1, N):
            index_weight[i] += index_weight[i - 1]
        
        print(index_weight)
        
        sorted_w = sorted(list(index_weight.keys()), key=lambda i: -index_weight[i])
        sorted_n = sorted(nums, key=lambda n: -n)
        
        ans = 0
        i = 0
        for idx in sorted_w:
            if index_weight[idx] > 0:
                ans += index_weight[idx] * sorted_n[i]
                i += 1
        
        return ans % (10 ** 9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:    
        MOD = (10 ** 9 + 7)
        
        events = []
        for l, r in requests:
            events.append((l, 1))
            events.append((r + 1, -1))
        events.sort()
        
        request_counts = [0 for i in range(len(nums))]
        j = 0
        total = 0
        for i in range(len(request_counts)):
            while j < len(events) and events[j][0] == i:
                total += events[j][1]
                j += 1
            request_counts[i] = total
            
        request_counts.sort()
        nums.sort()
        
        result = 0
        for r, n in zip(request_counts, nums):
            result = (result + r * n) % MOD
            
        return result
        
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        freq = [0]*(len(nums)+1)
        
        for a,b in requests:
            freq[a] += 1
            freq[b+1] -= 1
            
        for i in range(1,len(freq)):
            freq[i] = freq[i]+freq[i-1]
            
        freq.sort(reverse = True)
        nums.sort(reverse = True)
        ans = 0
        
        for i in range(len(nums)):
            ans += freq[i]*nums[i]
            
            
        return ans%1000000007
        
            
            
        
            


from collections import defaultdict
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # scan line
        points = []
        for req in requests:
            points.append([req[0], 0]) # 0 - start
            points.append([req[1], 1]) # 1 - end
            
        points.sort(key=lambda e:(e[0], e[1]))
        freqCnt = defaultdict(int)

        pos = None
        cnt = 0
        for p in points:     
            if pos != None:
                # set right end of current interval depending on current point (start or end)
                if p[1] == 0:
                    freqCnt[cnt] += p[0] - pos
                else:
                    freqCnt[cnt] += p[0] - pos + 1
            
            if p[1] == 0:
                cnt += 1
            else:
                cnt -= 1
                
            if cnt == 0:
                pos = None
            else:
                # set left end of next interval depending on current point (start or end)
                if p[1] == 0:
                    pos = p[0]
                else:
                    pos = p[0] + 1
            
        nums.sort(reverse=True)
        result = 0
        i = 0
        for k, v in sorted(list(freqCnt.items()), reverse=True):
            result += k * sum(nums[i:i+v])
            i += v
            
        return result % (10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:

        def getFreq():            
            minVal = sys.maxsize
            maxVal = 0

            freq = [0 for _ in range(len(nums)+1)]   

            for i in range(len(requests)): 
                low = requests[i][0]  
                freq[low] = freq[low] + 1
                high = requests[i][1]  
                freq[high + 1] = freq[high + 1] - 1
                if low < minVal:  
                    minVal = low  
                if high > maxVal: 
                    maxVal = high  
                
                # print(freq)
            
            for i in range(minVal+1, maxVal + 2):  
                freq[i] = freq[i] + freq[i - 1]
            
            return freq[:-1]  
         
        answer = 0
        freq = getFreq()
        # print(freq)
        freq = sorted(freq)
        nums = sorted(nums)
        # print(freq, nums)
        for i in range(1, len(nums)+1):
            answer = (answer + (freq[i-1]*nums[i-1])) %(10**9+7)
        # print('-----------')
        return answer

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0] * (n + 1)
        for i, j in requests:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(nums)):
            res += v * c
        return res % (10**9 + 7)
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        events = []
        for s, e in requests:
            events.append((s, \"a\"))
            events.append((e, \"b\"))
        events.sort()
        ne = len(events)
        depth, stabs = 0, []
        event_i = 0
        x, kind = events[0]
        for i in range(len(nums)):
            while x <= i and kind == \"a\" and event_i < ne:
                depth += 1
                event_i += 1
                if event_i >= ne: break
                x, kind = events[event_i]
            stabs.append(depth)
            while x <= i and kind == \"b\" and event_i < ne:
                depth -= 1
                event_i += 1
                if event_i >= ne: break
                x, kind = events[event_i]
        stabs.sort(reverse = True)
        nums.sort(reverse = True)
        ans = 0
        for freq, val in zip(stabs, nums):
            ans += freq*val
            ans %= MOD
        return ans % MOD
        

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort()
        times = [0] * (len(nums) + 1)
        for a, b in requests:
            times[a] += 1
            times[b+1] -= 1
        for i in range(1, len(times)):
            times[i] += times[i-1]
        times.pop()
        times.sort()
        return sum(a*b for a, b in zip(times, nums)) % (10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        
        ctr = collections.Counter()
        pq = []
        
        for s, e in requests:
            heapq.heappush(pq, (s, 1))
            heapq.heappush(pq, (e+1, -1))
        
        # print(pq)
        counts = 0
        for k in range(n):
            while pq and pq[0][0] == k:
                counts += heapq.heappop(pq)[1]
            ctr[k] = counts
        
        nums.sort()
        ans = 0
        for idx, ct in ctr.most_common():
            ans += nums.pop() * ct
        return ans % (10**9+7)


from typing import List
import collections
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        sweeplines = []
        for i,j in requests:
            sweeplines.append((i,1))
            sweeplines.append((j+1,-1))
        sweeplines.sort()
        sweeplines=collections.deque(sweeplines)
        freq=0
        freqs=[]
        for i in range(len(nums)):
            while sweeplines and sweeplines[0][0]==i:
                freq+=sweeplines[0][1]
                sweeplines.popleft()
            freqs.append(freq)
        freqs.sort(reverse=True)
        nums.sort(reverse=True)
        ans=sum([freq*num for freq,num in zip(freqs,nums)])
        return ans%(10**9 + 7)
            








class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        i_count = [0] * N

        for start, end in requests:
            i_count[start] += 1

            if end + 1 < N:
                i_count[end + 1] -= 1

        for i in range(1, N):
            i_count[i] += i_count[i - 1]

        return sum(a * b for a, b in zip(sorted(i_count), sorted(nums))) % 1000000007

from collections import defaultdict

MOD = int(1e9 + 7) 

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        sorted_nums = sorted(nums, reverse=True)
        temp = [0 for _ in range(len(nums))]
        sum_ = 0
        for r in requests:
            temp[r[0]] += 1
            if r[1]+1 < len(nums):
                temp[r[1]+1] -= 1
            
        temp2 = []
        count = 0
        for x in temp:
            count += x
            temp2.append(count)
        sorted_counter = sorted(temp2, reverse=True)
        
        # print(sorted_nums)
        # print(len(sorted_nums))
        # print(temp)
        # print(len(temp))
        # print(sorted_counter)
        
        for counter in sorted_counter:
            sum_ += (counter * sorted_nums.pop(0)) % MOD
        
        # print(sorted_nums)
        
        return sum_ % MOD
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        i_count = Counter()
        first = float('inf')
        last = -first

        for start, end in requests:
            i_count[start] += 1
            i_count[end + 1] -= 1
            first = min(first, start)
            last = max(last, end)

        q = []
        s = 0

        for p in range(first, last + 1):
            s += i_count[p]
            q.append(-s)

        heapq.heapify(q)

        ans = 0
        nums.sort()

        while q:
            ans = (ans + nums.pop() * -heapq.heappop(q)) % 1000000007

        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        requestCount = defaultdict(int) #Number of request per index
        
        #Create a min-heap of the start and end intervals.
        begHeap = []
        endHeap = []
        for req in requests:
            heapq.heappush(begHeap, req[0])
            heapq.heappush(endHeap, req[1]+1)
        
        poppedCount = 0 #Keeps track of how many intervals we have entered without exiting. (Currently active)
        for i in range(len(nums)):
            
            while begHeap and begHeap[0] <= i:
                heapq.heappop(begHeap)
                poppedCount += 1
                
            while endHeap and endHeap[0] <= i:
                heapq.heappop(endHeap)
                poppedCount -= 1
                continue
            requestCount[i] = poppedCount
        
        #Then we simply get the highest interval frequency and match with the highest nums
        sortedRequest = sorted(list(requestCount.items()), key = lambda x: -x[1])
        nums.sort(key = lambda x: -x)
        
        out = 0
        for n, s in zip(nums, sortedRequest):
            out += (n*s[1])
            
        return out % (pow(10, 9)+7)


MODNUM = 10 ** 9 + 7
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        M = len(requests)
        ct = [0] * N
        requests = sorted(requests)
        i, j = 0, 0
        used = []
        
        for k in range(N):
            while i < M and k >= requests[i][0]:
                a, b = requests[i]
                heappush(used, b)
                i += 1
            while len(used) > 0 and k > used[0]:
                heappop(used)

            ct[k] = len(used)
            # print(ct, i, j)
            
        ct = sorted(ct, reverse=True)
        nums = sorted(nums, reverse=True)
        # print(ct)
        # print(nums)
        
        res = 0
        for n, c in zip(nums, ct):
            if c == 0:
                break
            res += n * c
            
        return res % MODNUM
        
        
            
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        s = sorted([a for a, _ in requests])
        e = sorted([a for _, a in requests])
        freq = []
        for i in range(len(nums)):
            start_after = bisect.bisect_right(s, i)
            end_before = bisect.bisect_left(e, i)
            freq.append(start_after - end_before)
        freq.sort(reverse=True)
        nums.sort(reverse=True)
        res = 0
        for i, f in enumerate(freq):
            res += int(f * nums[i] % (1e9 + 7))
        return int(res % (1e9 + 7))

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        nums.sort(reverse=True)
        N = len(nums)
        
        events = [0]*(N + 1)
        
        for start, end in requests:
            events[start] += 1
            events[end + 1] -= 1

        for i in range(1, len(events)):
            events[i] += events[i - 1]

        res = 0
        events.pop()

        events.sort()
        nums.sort()
        
        for num, size in zip(nums, events):
            res += num*size
        
        return res % MOD

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        freqs = [0] * (len(nums) + 1)
        for s, e in requests:
            freqs[s] += 1
            freqs[e + 1] -= 1
        freqs.pop()
        f = 0
        for i, x in enumerate(freqs):
            f += x
            freqs[i] = f
        nums.sort()
        freqs.sort()
        result = 0
        for n, f in zip(nums, freqs):
            result += f * n
        return result % 1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        nums.sort()
        n = len(nums)
        weights = [0] * n
        for start, end in requests:
            weights[start] += 1
            if end + 1 < n:
                weights[end+1] -= 1
        for i in range(1, n):
            weights[i] += weights[i-1]
        weights.sort()
        ans = 0
        for num, weight in zip(nums, weights):
            ans += num * weight
            ans %= MOD
        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        requests.sort(reverse=True)
        cur = []
        height = []
        for i in range(len(nums)):
            while requests and requests[-1][0] <= i:
                heapq.heappush(cur, requests.pop()[1])
            while cur and cur[0] < i:
                heapq.heappop(cur)
            height.append(len(cur))
        print(height)
        height.sort()
        nums.sort()
        return sum(n * h for n, h in zip(nums, height)) % (10 ** 9 + 7)



class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        
        tmp = sorted([k for i, j in requests for k in [(i, 1), (j + 1, -1)]])
        counter = collections.defaultdict(int)
        last = 0
        now = 0
        for ind, delta in tmp:
            counter[now] += ind - last
            last = ind
            now += delta
        
        nums.sort(reverse=True)
        l = len(nums)
        result = 0
        now = 0
        for count, num in sorted(list(counter.items()), reverse=True):
            result += sum(nums[now: now + num]) * count
            now += num
            if now > l:
                break
        
        return result % MOD
        
#         nums.sort(reverse=True)
#         # nums.sort()
        
#         starts = collections.deque(sorted(i for i, j in requests))
#         ends = collections.deque(sorted(j for i, j in requests))
#         counter = collections.defaultdict(int)
#         now = 0
#         prev = 0
#         while starts or ends:
#             if starts and ends:
#                 if starts[0] > ends[0]:
#                     counter[now] += ends[0] - prev + 1
#                     now -= 1
#                     prev = ends[0] + 1
#                     ends.popleft()
#                 else:
#                     counter[now] += starts[0] - prev
#                     now += 1
#                     prev = starts[0]
#                     starts.popleft()
#             else:
#                 counter[now] += ends[0] - prev + 1
#                 now -= 1
#                 prev = ends[0] + 1
#                 ends.popleft()
        
#         # counter = collections.defaultdict(int)
#         # for start, end in requests:
#         #     for i in range(start, end + 1):
#         #         counter[i] += 1
#         result = 0
#         now = 0
#         for i in sorted(counter, reverse=True):
#             c = counter[i]
#             result += sum(nums[now: now + c]) * i
#             now += c
#         # for i, j in zip(sorted(counter.values(), reverse=True), nums):
#             # result += i * j
#         return result % (10 ** 9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        '''
        factors = [0]*len(nums)
        for a,b in requests:
            for i in range(a,b+1):
                factors[i] += 1
        factors.sort()
        nums.sort()
        out = 0
        for i in range(len(nums)):
            out = (out + nums[i]*factors[i])%(10**9+7)
        return out
        '''
        
        pts = []
        for a, b in requests:
            pts.append((a,-1))
            pts.append((b,+1))
        pts.sort()
        dic = defaultdict(int)
        factor, prev = 0, 0
        for a, d in pts:
            if d == -1:
                dic[factor] += (a-prev)
                prev = a
            else:
                dic[factor] += (a+1-prev)
                prev = a+1
            factor += -d
        nums.sort(reverse=True)
        prev, out = 0, 0
        dic = sorted(list(dic.items()), key=lambda x: x[0], reverse=True)
        for factor, length in dic:
            for k in range(prev, prev + length):
                out = (out + factor*nums[k])%(10**9 + 7)
            prev += length
        return out


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        ranks = [0] * (len(nums) + 1)
        requests.sort()
        
        for start, end in requests:
            ranks[start] += 1
            ranks[end + 1] -= 1
        
        nums.sort()
        for i in range(1, len(nums) + 1):
            ranks[i] += ranks[i - 1]
        
        ranks = ranks[:len(nums)]
        
        return sum(x * y for x, y in zip(sorted(nums), sorted(ranks))) % MOD

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        '''
        Tricky part is finding the permutation that will result in maximum
        sum of the requests
        
        Looping through all permutations will likely TLE
        
        Setup nums in a way such that requests is maximized.
        
        Do it in greedy way + sort
        Have the max values be at the largest request interval
        
        How to deal with overlapping requests
        
        Largest number goes in index with most
        overlappings, second largest goes to index
        with second most overlappings etc.
        
          -
          - - -
        - - -
        0 1 2 3 4 5
        1 2 3 4 5 9
         
        requests
        [[0,2],[1,3],[1,1]]
        
        overlaps
        
        0 1 2 3 4 5
        1 3 2 1 0 0
        
        1 2 0 3 4 5
        3 2 1 1 0 0
        
        0 1 2 3 4 5
        4 9 5 3 2 1
        
        For each index calculate the number of request that overlap it
        Better to do this the other way around.
        
        This still TLEs
        
        O(nlogn)
        
        Your implementation is not actually O(nlogn) see
        comment in code
        '''
        if not nums or not requests: return 0
        
        overlaps = [(i, 0) for i in range(len(nums) + 1)]
        for start, end in requests:
            overlaps[start] = (overlaps[start][0], overlaps[start][1] + 1)
            overlaps[end + 1] = (overlaps[end + 1][0], overlaps[end + 1][1] - 1)
            
        for i in range(1, len(overlaps)):
            overlaps[i] = (overlaps[i][0] , overlaps[i][1] + overlaps[i - 1][1])
        
        overlaps.pop()
        overlaps.sort(key=lambda tup: tup[1], reverse=True)
        nums.sort()
        max_permutation = [0] * len(nums)
        for i, freq in overlaps:
            max_permutation[i] = nums[-1]
            nums.pop()
        
        prefix_sum = [max_permutation[0]]
        for i in range(1, len(max_permutation)):
            prefix_sum.append(prefix_sum[i - 1] + max_permutation[i])
        
        sum = 0
        for start, end in requests:
            right = prefix_sum[end]
            left = 0 if start == 0 else prefix_sum[start - 1]
            sum += right - left
        
        return sum % (10**9 + 7)

    
    def maxSumRangeQuery_1(self, nums: List[int], requests: List[List[int]]) -> int:
        '''
        Discuss Solution thats faster at detecting
        the number of requests that overlap an index.
        
        Key Idea have array t, loop
        through requests [[start, end] ...]
        
        Make t[start] += 1 to indicate
        every index after start is counted once
        for this request overlap
        Make t[end + 1] -= 1 to indicate
        every index after end + 1 is counted one less
        for this request overlap
        
        The prefix sum of array t tells us
        the number of requests that overlap
        an index
        
        requests
        [[0,2],[1,3],[1,1]]
        
          -
          - - -
        - - -
        0 1 2 3 4 5
        1 2 3 4 5 9
        
        t
        0  1  2  3  4  5  6
        1  2 -1 -1 -1
        
        t_prefix
        0  1  2  3  4  5  6
        1  3  2  1  0  0  0
        
        t.pop to remove index 6
        Sort both nums and t and
        use zip to line them up
        This matches most frequently
        overlapped index with biggest
        num.
        
        nums
        1 2 3 4 5 9
        t
        0 0 1 1 2 3
        
        Multiply because index i gets overlapped
        t[i] times so the nums value of mapping
        also gets mulitplied that number of times
        for the sum
        
        nums[i] * t[i]
        0 0 3 4 10 27
        
        sum of final = 44
        '''
        t = [0] * (len(nums) + 1)
        
        for start, end in requests:
            t[start] += 1
            t[end + 1] -= 1
            
        for i in range(1, len(nums)):
            t[i] += t[i - 1]
        
        nums.sort()
        t.pop() # Makes it so t matches length with nums
        t.sort()

        return sum(a*b for a, b in zip(nums, t)) % (10**9 + 7)
            
        
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        len_nums = len(nums)
        frequencies = [0] * (len_nums + 1)
        for start, end in requests:
            frequencies[start] += 1
            frequencies[end + 1] -= 1
        for k in range(1, len_nums):
            frequencies[k] += frequencies[k - 1]
        frequencies.sort(reverse=True)
        nums.sort(reverse=True)
        max_sum = 0
        for num, frequency in zip(nums, frequencies):
            max_sum += num * frequency
        return max_sum % (10**9 + 7)


class Solution:
    
    def update(self,d,s,e):
        d[s]+=1
        d[e+1]-=1
        
        
        
        
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort()
        n=len(nums)
        d=[0]*(n+1)
        m=10**9+7
        for i in range(len(requests)):
            s=requests[i][0]
            e=requests[i][1]
            self.update(d,s,e)
                
     

        for i in range(0,n):
            if i==0:
                continue
            else:
                d[i]=d[i]+d[i-1]
                
        d.pop()
                
        d.sort()
        
        count=0
        for i in range(n):
            count=(count+d[i]*nums[i])%m
            
        return count%m
        
        


class Solution:
    def maxSumRangeQuery(self, A: List[int], E: List[List[int]]) -> int:
        MOD = 10**9 + 7
        cts = collections.Counter()
        for a,b in E:
            cts[a] += 1
            cts[b+1] -= 1
        N = len(A)
        for i in range(N):
            cts[i] += cts[i-1]
        X = [(i, cts[i]) for i in range(N)]
        X.sort(key = lambda a: a[1])
        A.sort()
        res = [0]*N
        for i in range(N):
            res[X[i][0]] = A[i]
        hardproblem = [0]
        for a in res:
            hardproblem.append(hardproblem[-1] + a)
        total = 0
        for a,b in E:
            total = ( total + hardproblem[b+1] - hardproblem[a]) % MOD
        return total

from itertools import permutations

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort(reverse=True)
        count = [0 for i in range(len(nums) + 1)]
        for start, end in requests:
            count[start] += 1
            count[end + 1] -= 1
        for i in range(1, len(count)):
            count[i] += count[i - 1]
        count.sort(reverse=True)
        maxSum = 0
        for i in range(len(count) - 1):
            maxSum += count[i] * nums[i]
        return maxSum % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        weights = defaultdict(int)
        requests.sort()
        prev, ends = None, []
        for l, r in requests:
            while ends and ends[0] < l:
                weight = len(ends)
                end = heappop(ends)
                weights[weight] += (end - prev) + 1
                prev = end + 1
                
            if not ends:
                prev = l
                ends = [r]
            else:
                weight = len(ends)
                weights[weight] += (l - prev)
                prev = l
                heappush(ends, r)
                
        while ends:
            weight = len(ends)
            end = heappop(ends)
            weights[weight] += (end - prev) + 1
            prev = end + 1  
        
        total = 0
        nums.sort(reverse=True)
        l = 0
        for weight in sorted(list(weights.keys()), reverse=True):
            length = weights[weight]
            total += (sum(nums[l: l + length]) * weight) % MOD
            l = l + length
        return total % MOD
            
                


import heapq
import math

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        starts = []
        ends = []
        
        for start, end in requests:
            heapq.heappush(starts, (start, end))
        
        curr_start = None
        new_ranges = []
        
        while len(starts) > 0:
            peek_start = starts[0]
            
            peek_end = ends[0] if len(ends) > 0 else (math.inf, math.inf)
            if peek_end[0] < peek_start[0]:
                new_ranges.append((curr_start, peek_end[0], len(ends)))
                while len(ends) > 0 and ends[0][0] == peek_end[0]:
                    heapq.heappop(ends)
                curr_start = peek_end[0] + 1
            elif peek_end[0] > peek_start[0]:
                if len(ends) > 0:
                    new_ranges.append((curr_start, peek_start[0] - 1, len(ends)))
                while len(starts) > 0 and starts[0][0] == peek_start[0]:
                    elt = heapq.heappop(starts) 
                    heapq.heappush(ends, (elt[1], elt[0]))
                curr_start = peek_start[0]
            else:
                new_ranges.append((curr_start, peek_end[0] - 1, len(ends)))
                
                while len(starts) > 0 and starts[0][0] == peek_start[0]:
                    elt = heapq.heappop(starts) 
                    heapq.heappush(ends, (elt[1], elt[0]))
                
                new_ranges.append((peek_end[0], peek_end[0], len(ends)))
                
                while len(ends) > 0 and ends[0][0] == peek_end[0]:
                    heapq.heappop(ends)  
                
                curr_start = peek_end[0] + 1
         
        while len(ends) > 0:
            peek_end = ends[0]
            new_ranges.append((curr_start, peek_end[0], len(ends)))
            while len(ends) > 0 and ends[0][0] == peek_end[0]:
                heapq.heappop(ends)
            curr_start = peek_end[0] + 1
           
        counts = [0] * len(nums)
        for start, end, f in new_ranges:
            for i in range(start, end + 1):
                counts[i] += f  
        sorted_indices = sorted(counts)
        sorted_elts = sorted(nums)
        

        res = 0
        while len(sorted_elts) > 0:
            res += sorted_elts.pop() * sorted_indices.pop()
        return res % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort()
        dp = [0] *(len(nums) + 1)
        for x,y in requests:
            dp [x] += 1 
            dp [y +1] -= 1
        
        for i in range(1,len(nums) + 1 ):
            dp[i] += dp[i-1]
         
        res = 0
        for v, c in zip(sorted(dp[:-1]), sorted(nums)):
            res += v * c
        return res % (10**9 + 7)
    
    # 0,1,2,1,1,0
    # 0 1,0,0,-1,0
    # 1,0,1,0,-1,0


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mod=10**9+7
        n=len(nums)
        ops=[]
        for request in requests:
            ops.append((request[0],1))
            ops.append((request[1]+1,-1))
        ops.sort()
        nums.sort()
        counts=[]
        cur=0
        count=0
        for idx in range(n):
            while cur<len(ops) and idx==ops[cur][0]:
                count+=ops[cur][1]
                cur+=1
            counts.append(count)
        counts.sort()
        return sum([c*num for c,num in zip(counts,nums)]) % mod

from collections import deque

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        counter = [0] * n
        enter = list()
        leave = list()
        for l, r in requests:
            enter.append(l)
            leave.append(r)
        
        enter.sort()
        leave.sort()
        
        ei = 0
        li = 0
        en = len(requests)
        cnt = 0
        for i in range(n):
            while ei < en and enter[ei] == i:
                ei += 1
                cnt += 1
            counter[i] = cnt
            while li < en and leave[li] == i:
                li += 1
                cnt -= 1
        #print(counter)
        
        vals = []
        for i, cnt in enumerate(counter):
            vals.append([-cnt, i])
        vals.sort()
        #print(vals)
        
        res = 0
        nums.sort()
        for i, num in enumerate(nums[::-1]):
            res -= num * vals[i][0]
            res = res % (10**9+7)
        # for val, num zip(vals, nums[::-1]):
        #     res += num * (-val[0])
        return res
            
                    
                    


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10 **9 + 7
        n = len(nums)
        count = [0] * (n)
        for s, e in requests:
            count[s] += 1
            if e + 1 < n:
                count[e + 1] -= 1
        for i in range(1, n):
            count[i] += count[i-1]
        count.sort()
        nums.sort()
        ans = 0
        for c, a in zip(count, nums):
            ans = (ans + c * a) % MOD
        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort()
        n = len(nums)
        bit = [0] * (n + 1)
        def query(i):
            s = 0
            while i > 0:
                s += bit[i]
                i -= (i & -i)
            return s
        
        def insert(key, value):
            while key <= n:
                bit[key] += value
                key += (key & -key)
        
        for request in requests:
            insert(request[0] + 1, 1)
            insert(request[1] + 2, -1)
        
        vals = sorted([query(i + 1) for i in range(n)])
        return sum(x * y for x, y in zip(vals, nums)) % 1_000_000_007
    


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        counts = [0] * 100001
        for start, end in requests:
            counts[start] += 1
            counts[end + 1] -= 1
        for i in range(100001):
            counts[i] += counts[i-1]
        result, mod = 0, 10 ** 9 + 7
        for num, count in zip(sorted(nums, reverse=True), sorted(counts, reverse=True)):
            result = (result + num * count) % mod
        return result


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        c = [0] * n
        a = [0] * n
        b = [0] * n
        for x in requests:
            a[x[0]] += 1
            b[x[1]] += 1
        now = 0
        for i in range(n):
            now += a[i]
            c[i] = now
            now -= b[i]
        c.sort()
        nums.sort()
        ret = 0
        for i in range(n):
            ret += c[i] * nums[i]
        ret %= 10 ** 9 + 7
        return ret

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        start_dic, end_dic = {}, {}
        modd = 10**9 + 7
        for req in requests:
            st, ed = req
            start_dic[st] = start_dic.get(st, 0) + 1
            end_dic[ed] = end_dic.get(ed, 0) + 1
        
        idx_cnt = []
        cnt = 0
        for i in range(n):
            if i in start_dic:
                cnt += start_dic[i]
            if i-1 in end_dic:
                cnt -= end_dic[i-1]
            idx_cnt.append(cnt)
        
        idx_cnt.sort()
        nums.sort()
        
        res = [idx_cnt[i]*nums[i] for i in range(n)]
        ans = 0
        for x in res:
            ans = (ans + x) % modd
        return ans
        
        # ele[0]*ele[1] for ele in zip([idx_cnt, nums])


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        request_counts = [0] * (len(nums) + 1)
        
        for start, end in requests:
            request_counts[start] += 1
            request_counts[end + 1] -= 1
        
        cur_count = 0
        for i in range(len(nums) + 1):
            cur_count += request_counts[i]
            request_counts[i] = cur_count
        
        nums.sort(reverse=True)
        
        sorted_idxs = sorted(range(len(nums) + 1), key=lambda i: request_counts[i], reverse=True)
        
        # perm = [0] * len(nums)
        ans = 0
        
        for idx, num in zip(sorted_idxs, nums):
            ans += num * request_counts[idx]
        
        return ans % int(1e9 + 7)    

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        req=[0]*(len(nums)+1)
        # Adding 1 for all elements in req(r[0]:r[1]+1) costs too much time.
        for r in requests:
            req[r[0]]+=1
            req[r[1]+1]-=1
        for i in range(1,len(req)):
            req[i]+=req[i-1]
        req=sorted(req, reverse=True)
        nums=sorted(nums, reverse=True)
        answer=0
        for i in range(len(nums)):
            if req[i]==0 or nums[i]==0:
                return answer%1000000007
            answer+=req[i]*nums[i]
        return answer%1000000007

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        \"\"\"
        Assume:
        1. list, list -> int
        2. only find sum, permutation is not unique
        3. nums is not sorted
        
        
        Algorithm:
        sort nums
        
        in requests, count number of coverage for each index. 
        counts = [c0, c1]
        put (c0, 0), (c1, 1) into maxHeap
        popout maxHeap, each index gets the assigned element from largest to smallest to form new nums
        
        calculate sum of requests in new nums
        
        Complexity:
        time: max(O(nlogn), O(mn))
        space: O(n)
        
        Follow up:
        1. use LinkedHashMap
        2. 
        
        \"\"\"
        if not nums:
            return -1 # rise IllegalInputArgumentException
        
        MOD = 10 ** 9 + 7
        result, n, m = 0, len(nums), len(requests)
        counts = [0 for _ in range(n)]
        max_heap = []
        
        # O(m*n)
        #for i in range(m):
        #    for j in range(requests[i][0], requests[i][1] + 1):
        #        counts[j] += 1
                
        # O(max(m, n)): use sweep line
        records = []
        for i in range(m):
            records.append([requests[i][0], 1])
            records.append([requests[i][1]+1, -1])
        for index, delta in sorted(records):
            if index < n:
                counts[index] += delta
        for i in range(n):
            if i != 0:
                counts[i] = counts[i] + counts[i-1]
        
        for i in range(n):
            heapq.heappush(max_heap, (-counts[i], i))
        
        # O(nlogn)
        nums.sort()
        new_nums, cur_max = [0 for _ in range(n)], n - 1
        while max_heap and cur_max >= 0:
            cur = heapq.heappop(max_heap)
            new_nums[cur[1]] = nums[cur_max]
            cur_max -= 1
        
        prefixsum = [0 for _ in range(n)]
        for i in range(n):
            if i == 0:
                prefixsum[i] = new_nums[i]
            else:
                prefixsum[i] = prefixsum[i-1] + new_nums[i]
        # print(f'counts:{counts}, new_nums:{new_nums}')
        for i in range(m):
            result += prefixsum[requests[i][1]] - prefixsum[requests[i][0]] + new_nums[requests[i][0]]
        return result % MOD
        
        
        
        

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        imos = [0] * (n + 1)
        for l, r in requests:
            imos[l] += 1
            imos[r + 1] -= 1
        for i in range(n):
            imos[i + 1] += imos[i]
        del imos[-1]
        
        ans = 0
        for i, v in zip(sorted(nums), sorted(imos)):
            ans += i * v
            ans %= 10 ** 9 + 7
        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], req: List[List[int]]) -> int:
        l=[0]*(len(nums)+1)
        nums.sort(reverse=True)
        for i in req:
            l[i[0]]+=1
            l[i[1]+1]-=1
        for i in range(1,len(l)):
            l[i]+=l[i-1]
        l=l[:-1]    
        #print(l)        
        d=collections.defaultdict(list)
        for i in range(len(l)):
            d[l[i]].append(i)
        di=collections.OrderedDict(sorted(d.items()))   
        #print(di)
        k=0
        ans=[0]*len(nums)
        for i in di:
            for j in di[i]:
                ans[j]=nums[len(nums)-k-1]
                k+=1
        #return ans        
        c=0
        print(ans)    
        for i in range(1,len(ans)):
            ans[i]+=ans[i-1]
        
        ans.insert(0,0)
        print(ans)   
        for i in req:
            c+=(ans[i[1]+1]-ans[i[0]])
        return c%(10**9+7)
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        m = len(requests)
        d = [0] * len(nums)
        # R = sorted(requests, key = lambda x:(x[0],-x[1]))
        R = sorted(requests)
        q = []
        j = 0
        for i in range(n):
            while q and q[0] < i:
                heapq.heappop(q)
            while j < m and R[j][0] <= i:
                heapq.heappush(q, R[j][1])
                j += 1
            d[i] = len(q)
        
        # print(d)
        
        # d.sort(reverse=1)
        # nums.sort(reverse=1)
        # ret = 0
        # j = 0
        # for i in d:
        #     ret += i * nums[j]
        #     j += 1
        # return ret % (10 ** 9 + 7)
        
        d.sort()
        nums.sort()
        ret = 0
        for i,j in zip(nums,d):
            ret += i*j
        return ret % (10 ** 9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        fq = [0]*n
        for l,r in requests:
            fq[l]+=1
            if r<n-1:
                fq[r+1]-=1
        for i in range(n):
            fq[i]=(fq[i-1] if i!=0 else 0)+fq[i]
        nums.sort()
        fq.sort()
        ans = 0
        for v,z in zip(nums,fq):
            ans = (ans+v*z)%(10**9+7)
        return ans


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0 for _ in range(n)]
        h = []
        requests.sort(key = lambda x: x[0])
        requests.append([float('inf'),float('inf')])
        cur = 0
        for s,e in requests:
            while h and h[0] < s:
                #all intervals in heap share [cur, h[0]]
                for i in range(cur, h[0]+1):
                    count[i] += len(h)
                cur = h[0]+1
                heapq.heappop(h)
            if s != float('inf'):
                for i in range(cur, s):
                    count[i] += len(h)
                cur = s
                heapq.heappush(h,e)
        mod = 10**9+7
        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod
                
                    


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        take = [False] * N
        MOD = 10**9 + 7
        
        fenwick = [0] * (N+1)
        
        def add(idx, val):
            idx += 1  # Make 1 based index
            while idx <= N:
                fenwick[idx] += val
                idx += idx & -idx
            
        
        def sum_(idx):
            idx += 1  # Make 1 based index
            ans = 0
            
            while idx > 0:
                ans += fenwick[idx]
                idx -= idx & -idx
            return ans
        
        def range_sum(a, b):
            return sum_(b) - sum_(a-1)
        
        for a, b in requests:
            # Make one based index
            add(a, 1)
            add(b+1, -1)
        
        occurrences = [0] * N
        
        for i in range(N):
            occurrences[i] = sum_(i)
        
        occ = sorted([(v,i) for i, v in enumerate(occurrences)], reverse=True)
        nums.sort()
        
        ans = 0
        for a, b in occ:
            if a:
                ans += (nums.pop() * a)
        
        
        return ans%MOD
        
                
    
    
#         vector<int> bit;  // binary indexed tree
#     int n;

#     FenwickTreeOneBasedIndexing(int n) {
#         this->n = n + 1;
#         bit.assign(n + 1, 0);
#     }

#     FenwickTreeOneBasedIndexing(vector<int> a)
#         : FenwickTreeOneBasedIndexing(a.size()) {
#         for (size_t i = 0; i < a.size(); i++)
#             add(i, a[i]);
#     }

#     int sum(int idx) {
#         int ret = 0;
#         for (++idx; idx > 0; idx -= idx & -idx)
#             ret += bit[idx];
#         return ret;
#     }

#     int sum(int l, int r) {
#         return sum(r) - sum(l - 1);
#     }

#     void add(int idx, int delta) {
#         for (++idx; idx < n; idx += idx & -idx)
#             bit[idx] += delta;
#     }


from collections import defaultdict as dd
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        nums.sort()
        n = len(nums)
        d = dd(int)
        new = [0]*n
        
        for r in requests :
            s, e = r
            new[s] += 1
            if e+1<n :
                new[e+1] -= 1
        c = 0
        for i in range(n) :
            
            new[i] += c
            c = new[i]
            
        new.sort()
        ans = 0
        for n in new[::-1] :
            ans = (ans +(n*nums[-1])% (10**9 + 7)) % (10**9 + 7)
            nums.pop()
        return ans 


import collections
import heapq
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        heapq.heapify(requests)
        count, end_heap, counter = 0, [], collections.Counter()
        for i in range(len(nums)):
            while requests and i >= requests[0][0]:
                count += 1
                heapq.heappush(end_heap, heapq.heappop(requests)[1])
            while end_heap and i > end_heap[0]:
                heapq.heappop(end_heap)
                count -= 1
            counter[i] += count
        heap = [-num for num in nums]
        heapq.heapify(heap)
        total, mod = 0, 10 ** 9 + 7
        for counts in sorted(list(counter.values()), reverse=True):
            total = (total - heapq.heappop(heap) * counts) % mod
        return total


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        freq = [0] * (n + 1)
        
        for i, j in requests:
            freq[i] += 1
            freq[j+1] -= 1
            
        for i in range(1, n + 1):
            freq[i] += freq[i - 1]
        freq = freq[:-1]    
        freq.sort()
        nums.sort()
        result = 0
        for i in range(n):
            result += freq[i] * nums[i]
        return result % 1_000_000_007

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        N = len(nums)
        index_weight = collections.defaultdict(int)
        for s, e in requests:
            index_weight[s] += 1
            index_weight[e + 1] -= 1
        
        for i in range(1, N + 1):
            index_weight[i] += index_weight[i - 1]
        
        sorted_w = sorted(list(index_weight.keys()), key=lambda i: -index_weight[i])
        sorted_n = sorted(nums, key=lambda n: -n)
        
        ans = 0
        i = 0
        for idx in sorted_w:
            if index_weight[idx]:
                ans += index_weight[idx] * sorted_n[i]
                i += 1
        
        return ans % (10 ** 9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        nums.sort()
        counter = [0] * (10 ** 5 + 2)
        
        for start, end in requests:
            counter[start] += 1
            counter[end+1] -= 1
        
        for i in range(1, len(counter)):
            counter[i] += counter[i-1]
        
        counter.sort()
        
        p1 = len(counter) - 1
        p2 = len(nums) - 1
        count = 0
        while counter[p1] > 0:
            count = (count + counter[p1] * nums[p2]) % (10**9+7)
            p1 -= 1
            p2 -= 1
        
        return count

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        nums.sort(reverse=True)
        
        index=[0]*len(nums)
        for start,end in requests:
            index[start]+=1
            if (end+1)<len(nums):
                index[end+1]-=1
            
        for i in range(1,len(nums)):
            index[i]+=index[i-1]
        
        
        index.sort(reverse=True)
        
        result=0
        for i in range(len(index)):
            freq=index[i]
            value=nums[i]
            
            if freq==0:
                break
            result+=value*freq
            
        return result%(10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        nums.sort(reverse=True)
        reqs = defaultdict(int)
        for start, end in requests:
            reqs[start] += 1
            reqs[end + 1] -= 1
        counts = defaultdict(int)
        h = 0
        last = -1
        for i in sorted(reqs.keys()):
            if h > 0:
                counts[h] += max(0, i - last)
            h += reqs[i]
            last = i
        res = 0
        i = 0
        n = len(nums)
        for h, c in sorted(list(counts.items()), reverse=True):
            for j in range(c):
                if i == n:
                    break
                num = nums[i]
                res += num * h
                res %= MOD
                i += 1
            if i == n:
                break
        return res


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        reqdict = collections.Counter()
        for request in requests:
            reqdict[request[0]] += 1
            reqdict[request[1]+1] -= 1
            
        increments = []
        prev = None
        mult = 0
        for key in sorted(reqdict.keys()):
            #print([key, reqdict[key]])
            if reqdict[key] != 0:
                if prev != None:
                    increments.append([mult, key-prev])
                prev = key
                mult += reqdict[key]
                
        increments.sort()
        #print(increments)
        
        x = len(increments)-1
        ans = 0
        nums.sort()
        for i in range(len(nums)-1, -1, -1):
            #print([nums[i], increments[x][0]])
            if x >= 0 and increments[x][0] > 0:
                ans = (ans + nums[i] * increments[x][0]) % (10**9 + 7)
                
            increments[x][1] -= 1
            if increments[x][1] == 0:
                x -= 1
                
        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n=len(nums)
        ind_counts=[0]*n
        nums2=ind_counts.copy()
        for i,j in requests:
            ind_counts[i]+=1
            if j+1<n:
                ind_counts[j+1]-=1
        for i in range(1,n):ind_counts[i]+=ind_counts[i-1]
        nums,ind_count=sorted(nums,reverse=True),sorted(list(range(n)),key=lambda x: -ind_counts[x])
        #print(ind_count)
        i=0
        while i<n and ind_counts[ind_count[i]]>0:
            nums2[ind_count[i]]=nums.pop(0)
            i+=1
        #print(nums2)
        ans=0
        for i in range(1,n):
            nums2[i]+=nums2[i-1]
        for i,j in requests:
            ans+=nums2[j]-nums2[i-1] if i-1>=0 else nums2[j]
        return ans%1000000007

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n=len(nums)
        rng=[0]*(n+1)
        for req in requests:
            l,r=req
            rng[l],rng[r+1]=rng[l]+1,rng[r+1]-1
        lst=[]
        for i in range(n):
            if i:
                rng[i]+=rng[i-1]
            lst.append(rng[i])
        # print(rng)
        # print(lst)
            
        ans=0
        return sum(num*cnt for num,cnt in zip(sorted(nums, reverse=True),sorted(lst, reverse=True)))%1000000007


from bisect import bisect_left as bl, bisect_right as br
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        arr=[]
        for i in range(len(requests)):
            arr.append((requests[i][0],-1))
            arr.append((requests[i][1],1))
        arr.sort()
        freq=[0]*len(nums)
        j=0
        s=0
        for i in range(len(nums)):
            while(j<len(arr) and arr[j][0]==i and arr[j][1]==-1):
                s+=1
                j+=1
            freq[i]=s
            while(j<len(arr) and arr[j][0]==i and arr[j][1]==1):
                s-=1
                j+=1
        freq.sort(reverse=True)
        nums.sort(reverse=True)
        ans=0
        for i in range(len(nums)):
            ans+=(freq[i]*nums[i])%(10**9+7)
        
        return ans%(10**9+7)
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mod = 10**9+7
        n = len(nums)
        
        freq = [0]*n
        for start, end in requests:
            freq[start] += 1
            if end+1 < n:
                freq[end+1] -= 1
        
        cur = 0
        for i in range(len(freq)):
            cur += freq[i]
            freq[i] = cur
        
        freq.sort(reverse = True)
        nums.sort(reverse = True)
        return sum([freq[i]*nums[i] for i in range(n)]) % mod

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        nums.sort()
        counter = [0] * (10 ** 5 + 2)
        
        for start, end in requests:
            counter[start] += 1
            counter[end+1] -= 1
        
        for i in range(1, len(counter)):
            counter[i] += counter[i-1]
        
        counter.sort()
        
        p1 = len(counter) - 1
        p2 = len(nums) - 1
        count = 0
        while counter[p1] > 0:
            count = (count + counter[p1] * nums[p2]) 
            p1 -= 1
            p2 -= 1
        
        return count % (10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        requests.sort()
        ct = []
        heap = []
        for i in range(len(nums)):
            while len(requests) != 0 and requests[0][0] == i:
                heapq.heappush(heap, requests[0][1])
                requests.pop(0)
            while len(heap) != 0 and heap[0] < i:
                heapq.heappop(heap)
            ct.append(len(heap))
        ct.sort(reverse=True)
        nums.sort()
        j = ans = 0
        for i in range(len(nums) - 1, -1, -1):
            ans += nums[i] * ct[j]
            j += 1
        return ans % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        heap_start = []
        heap_end = []
        for r in requests:
            heapq.heappush(heap_start, r[0])
            heapq.heappush(heap_end, r[1])
        current = 0
        p = []
        for n in range(len(nums)):
            while heap_start and heap_start[0]<=n:
                current += 1
                heapq.heappop(heap_start)
            while heap_end and heap_end[0]<n:
                current -= 1
                heapq.heappop(heap_end)
            p.append(current)
        
        heap = []
        for i, e in enumerate(p):
            heapq.heappush(heap, -e)
        ret = 0
        heapn = []
        for n in nums:
            heapq.heappush(heapn, -n)
        
        while heapn:
            n = heapq.heappop(heapn)
            ret +=  n*heapq.heappop(heap)
        return ret % (10**9+7)
            
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        f=[0 for i in range(len(nums)+1)]
        for i,j in requests:
            f[i]+=1
            f[j+1]-=1
        pf=[f[0]]
        for i in range(1,len(f)):
            pf.append(pf[i-1]+f[i])
        pf.sort(reverse=True)
        nums.sort(reverse=True)
        s=0
        for i in range(len(nums)):
            s+=pf[i]*nums[i]
        return(s%(10**9+7))


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        r = 10**5+1
        f = [0]*r
        for s, e in requests:
            f[s] += 1
            f[e+1] -= 1
        freq = {}
        curr = 0
        for i in range(r):
            curr += f[i]
            if curr != 0:
                freq[curr] = freq.get(curr, 0) + 1
        sol = 0
        nums.sort()
        for k, v in sorted([(k, v) for k, v in freq.items()], reverse=True):
            for _ in range(v):
                sol += k*nums.pop()
        return sol % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        import numpy
        weights=numpy.array([0]*len(nums))
        nums=numpy.array(nums)
        for l,r in requests: weights[l:r+1]+=1
        nums.sort() 
        weights.sort()
        return sum(nums*weights) % (10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        m = len(requests)
        d = [0] * len(nums)
        R = sorted(requests, key = lambda x:(x[0],-x[1]))
        q = []
        p = -1
        j = 0
        for i in range(n):
            while q and q[0] < i:
                heapq.heappop(q)
            while j < m and R[j][0] <= i:
                heapq.heappush(q, R[j][1])
                j += 1
            d[i] = len(q)
        
        # print(d)
        
        d.sort(reverse=1)
        nums.sort(reverse=1)
        ret = 0
        j = 0
        for i in d:
            ret += i * nums[j]
            j += 1
        return ret % (10 ** 9 + 7)

class BinaryIndexedTree:
    ''' index range from 0 to n-1'''
    def __init__(self, n):
        n += 1
        self.data = [0] * (n)
        self.n = n
    def add(self, index, value):
        index += 1
        while(index<self.n):
            self.data[index] += value
            index += index & -index
    def prefix(self, index):
        index += 1
        res = 0
        while(index):
            res += self.data[index]
            index ^= index & -index
        return res


class Solution:
    def maxSumRangeQuery(self, nums: List[int], query: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)
        BIT = BinaryIndexedTree(n+1)
        for l,r in query:
            BIT.add(l, 1)
            BIT.add(r+1, -1)
        count_index = []
        for i in range(n): 
            # this is O(n log n), can be optimized to O(n) by modifying BIT.data
            count_index.append((BIT.prefix(i), i))
        count_index.sort()
        nums.sort()
        ans = 0
        for (ct, _), v in zip(count_index, nums):
            ans += ct * v
            ans %= MOD
        return ans


class Solution:
    def maxSumRangeQuery(self, A: List[int], E: List[List[int]]) -> int:
        MOD = 10**9 + 7
        cts = collections.Counter()
        for a,b in E:
            cts[a] += 1
            cts[b+1] -= 1
        N = len(A)
        for i in range(N):
            cts[i] += cts[i-1]
        freqMap = [(i, cts[i]) for i in range(N)]
        freqMap.sort(key = lambda a: a[1])
        A.sort()
        res = [0]*N
        for i in range(N):
            res[freqMap[i][0]] = A[i]
        psum = [0]
        for a in res:
            psum.append(psum[-1] + a)
        total = 0
        for a,b in E:
            total = ( total + psum[b+1] - psum[a]) % MOD
        return total

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        nums = sorted(nums)
        mod = 10**9 + 7
        arry = [0]*(n+1)
        for x,y in requests:
            arry[x]+=1
            arry[y+1]-=1
        for i in range(1,n+1):
            arry[i]+=arry[i-1]
        q = []
        #print(arry)
        new_arry = [0]*n
        for idx,a in enumerate(arry):
            if a !=0:
                heapq.heappush(q,(-a,idx))
        while q:
            v,idx = heapq.heappop(q)
            if v==0:break
            new_arry[idx] = nums.pop()
        ans = 0
        for v,times in zip(new_arry,arry):
            ans+= v*times
        return ans%mod
            
        
            
            
                


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        m = len(requests)
        pre = [0 for i in range(n+1)]
        for (l,r) in requests:
            pre[l] += 1
            pre[r+1] -= 1
        cur = 0
        a = [0 for i in range(n)]
        for i in range(n):
            cur += pre[i]
            a[i] = cur
        # print(a)
        # print(nums)
        a.sort()
        nums.sort()
        ans = 0
        for i in range(n):
            ans += nums[i] * a[i]
            # print(nums[i], a[i])
        return int(ans % (1e9+7))


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        from queue import PriorityQueue
        from collections import defaultdict
        q = PriorityQueue()
        
        sorted_nums = sorted(nums)
        
        dig_dict = defaultdict(int)
        for r in requests:
            dig_dict[r[0]] += 1
            dig_dict[r[1]+1] -= 1
                
        for i in range(1, len(nums) + 1):
            dig_dict[i] += dig_dict[i-1]
            
        
        for k, v in list(dig_dict.items()):
            q.put((-v, k))
        
        final_pos = {}
        pointer = len(nums) - 1
        res = 0
        while q.qsize() > 0:
            # final_post[q.get()[1]] = sorted_nums[pointer]
            res += q.get()[0] * -1 * sorted_nums[pointer]
            pointer -= 1
        
        return res % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n, MOD, ans = len(nums), 10**9+7, 0
        count = [0]*(n+1)
        for s, e in requests:
            count[s]+=1
            count[e+1]-=1
        for i in range(1, n):
            count[i]+=count[i-1]
        have = sorted([c for c in count[:-1] if c], reverse=True)
        nums.sort(reverse=True)
        for a, b in zip(have, nums):
            ans+=(a*b)%MOD
            ans%=MOD
        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        arr = []
        for a, b in requests:
            arr.append([a, -1])
            arr.append([b, 1])
        cnt = 0
        pre = 0
        arr = sorted(arr)
        
        counter = Counter()
        for e, fg in arr:
            #print(cnt, e-pre)
            if fg == -1:
                counter[cnt] += e-pre
                pre = e
                cnt += 1
            else:
                counter[cnt] += e+1-pre
                pre = e+1
                cnt -= 1

        nums = [-e for e in nums] 
        heapq.heapify(nums)
        
        ans = 0
        for k in sorted(counter.keys())[::-1]:
            cnt = counter[k]
            while cnt!=0:
                cnt -= 1
                x = -heapq.heappop(nums)
                ans += x*k
                ans %= 10**9+7
        return ans
        
                


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        count = [0]*len(nums)
        for request in requests:
            count[request[0]] += 1
            if request[1] < len(nums)-1:
                count[request[1]+1] -= 1 
        for i in range(1, len(count)):
            count[i] += count[i-1]
        count.sort(reverse = True)
        nums.sort(reverse = True)
        res = 0
        for i in range(len(nums)):
            res += nums[i]*count[i]
        return res%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        events = [0]*(10**5+1)
        for start, end in requests:
            events[start] += 1
            events[end+1] -= 1
        for i in range(1, len(events)):
            events[i] += events[i-1]
        events.sort()
        nums.sort()
        modulo = 10**9+7
        answer = 0
        while nums and events:
            answer = (answer+nums.pop()*events.pop())%modulo
        return answer

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # n = len(nums), m = len(requests)
        # count all indices in requests - ind_count[ind] = count - time: O(m*n), space: O(n)
        # start_count = dict()
        # end_count = dict()
        # for s, e in requests:
        #     start_count[s] += 1
        #     end_count[e+1] += 1
        # ind_count = dict()
        # count = 0
        # for ind in range(n):
        #     count = count + start_count.get(ind, 0) - end_count.get(ind, 0)
        #     if count > 0:
        #         ind_count[ind] = count
        
        # sort the indices by counts in descending order - O(n*log(n))
        # inds = sorted(ind_count.keys(), lambda k: ind_count[k], reverse=True)
        # sort nums in descending order -> nums - O(n*log(n))
        # out = 0
        # for i, ind in enumerate(inds):
        #   out += ind_count[ind]*nums[i]
        # O(n)
        
        m, n = len(requests), len(nums)
        ind_count = dict()
        #for request in requests:
        #    for i in range(request[0], request[1]+1):
        #        ind_count[i] = ind_count.get(i, 0) + 1
        start_count = dict()
        end_count = dict()
        for s, e in requests:
            start_count[s] = start_count.get(s, 0) + 1
            end_count[e+1] = end_count.get(e+1, 0) + 1
        count = 0
        for ind in range(n):
            count = count + start_count.get(ind, 0) - end_count.get(ind, 0)
            if count > 0:
                ind_count[ind] = count
        
        inds = sorted(list(ind_count.keys()), key=lambda k: ind_count[k], reverse=True)
        nums = sorted(nums, reverse=True)
        out = 0
        for i, ind in enumerate(inds):
            out += ind_count[ind]*nums[i]
        return out % (10**9+7)
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        counts = collections.Counter()
        A = []
        for s, e in requests:
            A.append((s, -1))
            A.append((e, 1))
        A.sort()
        freq, h, last = [0] * n, 0, -1
        for index, direction in A:
            if last >= 0:
                for i in range(last + 1, index):
                    freq[i] = h
            last = index
            if direction == -1:
                h += 1
                freq[index] = max(freq[index], h)
            else:
                freq[index] = max(freq[index], h)
                h -= 1
                
        freq.sort(reverse = True)
        nums.sort(reverse = True)
        idx = res = 0
        for v in freq:
            res += nums[idx] * v
            idx += 1
        return res % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10 ** 9 + 7
        weights = defaultdict(int)
        requests.sort()
        prev, ends = requests[0][0], [requests[0][1]]
        for l, r in requests[1:]:
            while ends and ends[0] < l:
                weight = len(ends)
                end = heappop(ends)
                weights[weight] += (end - prev) + 1
                prev = end + 1
                
            if not ends:
                prev = l
                ends = [r]
            else:
                weight = len(ends)
                weights[weight] += (l - prev)
                prev = l
                heappush(ends, r)
                
        while ends:
            weight = len(ends)
            end = heappop(ends)
            weights[weight] += (end - prev) + 1
            prev = end + 1  
        
        total = 0
        nums.sort(reverse=True)
        l = 0
        for weight in sorted(list(weights.keys()), reverse=True):
            length = weights[weight]
            total += (sum(nums[l: l + length]) * weight) % MOD
            l = l + length
        return total % MOD
            
                


import math
import bisect
from typing import List
from collections import defaultdict


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:

        r_arr = [0] * len(nums)
        MOD = 10 ** 9 + 7
        for r in requests:
            r_arr[r[0]] += 1
            if r[1] < len(r_arr) - 1:
                r_arr[r[1] + 1] -= 1

        idxes = defaultdict(lambda: [])
        # curr = 0
        idxes[r_arr[0]].append(0)
        for r in range(1, len(r_arr)):
            # if r_arr[r] > 0:
            r_arr[r] += r_arr[r - 1]
            idxes[r_arr[r]].append(r)

        ks = list(idxes.keys())
        # print(ks)
        ks.sort(reverse=True)

        res_arr = [0] * len(nums)
        nums.sort(reverse=True)
        # print(nums)
        # print(r_arr)
        for k in ks:
            for ele in idxes[k]:
                res_arr[ele] = nums.pop(0)

        res = 0
        for i in range(len(res_arr)):
            res += (res_arr[i] * r_arr[i]) % MOD
        return res % MOD
        # return res


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        reqBounds = []
        for i in range(0, len(requests)):
            reqBounds.append((requests[i][0], 1))
            reqBounds.append((requests[i][1] + 1, -1))
        reqBounds = sorted(reqBounds, key=lambda x: (x[0], -x[1]))
        weight, curW, prev = [], 0, 0
        for i in range(0, len(reqBounds)):
            if reqBounds[i][1] == 1:
                weight.append((curW, reqBounds[i][0] - prev))
                curW += 1
                prev = reqBounds[i][0]
            else:
                weight.append((curW, reqBounds[i][0] - prev))
                curW -= 1
                prev = reqBounds[i][0]
        weight = sorted(weight, key=lambda x: -x[0])
        nums = sorted(nums, key=lambda x: -x)
        k, ans = 0, 0
        for i in range(0, len(weight)):
            for j in range(0, weight[i][1]):
                ans += weight[i][0] * nums[k]
                k += 1
        return ans % (10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        freqs = [0] * (len(nums) + 1)
        for s, e in requests:
            freqs[s] += 1
            freqs[e + 1] -= 1
        freqs.pop()
        f = 0
        for i, (x, n) in enumerate(zip(freqs, nums)):
            f += x
            freqs[i] = f
        nums.sort()
        freqs.sort()
        result = 0
        for n, f in zip(nums, freqs):
            result += f * n
        return result % 1000000007


from functools import cmp_to_key
def cmp(a,b):
    x1,y1 = a
    x2,y2 = b
    if(x1<x2):
        return -1
    elif(x1>x2):
        return -1
    else:
        if(y1=='S'):
            return 1
        else:
            return -1
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        N = len(nums)
        M = len(requests)
        l = [0 for i in range(N)]
        l1 = []
        for x,y in requests:
            l1.append((x,'S'))
            l1.append((y,'E'))
        l1.sort()
        i = 0
        j = 0
        ct = 0
        while(i<N):
            if(j>=2*M):
                l[i] = ct
                i += 1
            elif(i<l1[j][0]):
                l[i] = ct
                i += 1
            elif(i==l1[j][0]):
                ct1 = 0
                while(j<2*M and l1[j][0]==i):
                    if(l1[j][1]=='S'):
                        ct += 1
                    else:
                        ct1 += 1
                    j += 1
                l[i] = ct
                ct -= ct1
                i += 1
            else:
                j += 1
        
        '''for x,y in requests:
            for i in range(x,y+1):
                l[i] += 1'''
        
        l.sort(reverse=True)
        nums.sort(reverse=True)
        s = 0
        for i in range(N):
            s += l[i]*nums[i]
        return s%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        stream = []
        for start, end in requests:
            stream.append((start, 0))
            stream.append((end, 1))
        stream.sort()
        
        multiples = []
        cur_count = 0
        cur_event = 0
        for i in range(len(nums)):
            while cur_event < len(stream) and i == stream[cur_event][0] and stream[cur_event][1] == 0:
                cur_count += 1
                cur_event += 1
            multiples.append(cur_count)
            while cur_event < len(stream) and i == stream[cur_event][0] and stream[cur_event][1] == 1:
                cur_count -= 1
                cur_event += 1
        
        multiples.sort(reverse=True)
        nums.sort(reverse=True)
        
        return sum(num * multiple for num, multiple in zip(nums, multiples)) % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mex = 10**5
        mex+=5
        ans = [0 for i in range(mex)]
        for i in requests:
            x,y = i
            ans[x]+=1
            ans[y+1]-=1
        for i in range(1,mex):
            ans[i] = ans[i]+ans[i-1]
        nums.sort(reverse=True)
        freq = []
        for i in ans:
            if i!=0:
                freq.append(i)
        freq.sort(reverse=True)
        mod = 10**9
        mod+=7
        cnt = 0
        for i in range(min(len(freq),len(nums))):
            cnt = (cnt+((freq[i]*nums[i])%mod))%mod
        return cnt

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        total = []
        d = dict()
        for s,e in requests:
            d[e] = 1 if e not in d else d[e]+1
            if s:
                d[s-1] = -1 if s-1 not in d else d[s-1]-1
        ld = sorted(d.items())
        dtotal = []
        for k,v in ld[::-1]:
            if not dtotal:
                dtotal.append(v)
            else:
                dtotal.insert(0,dtotal[0]+v)
        cnt = [0]*len(nums)
        j = 0
        for i in range(len(ld)):
            while j <= ld[i][0]:
                cnt[j] = dtotal[i]
                j += 1
        cnt.sort()
        nums.sort()
        ans = 0
        for i in range(len(cnt)-1,-1,-1):
            if cnt[i] == 0:
                break
            ans += cnt[i]*nums[i]
        return ans%(10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        if nums==[] or requests==[]:
            return 0
        l=len(nums)
        freqs = [0]*(l+1)
        for request in requests:
            start, end = request
            freqs[start]+=1
            freqs[end+1]-=1
        # print(freqs)
        for i in range(1,l+1):
            freqs[i]+=freqs[i-1]
        nums = sorted(nums)
        freqs = sorted(freqs[:-1])
        # print(freqs)
        # print(nums)
        ans = 0
        for i in range(l):
            if freqs[i]==0:
                continue
            ans +=(freqs[i]*nums[i])
        return ans%((10**9)+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        cnt = [0] * n
        for l, r in requests:
            cnt[l] += 1
            if r + 1 < n:
                cnt[r + 1] -= 1
        
        partial_sum = 0
        for i in range(n):
            cnt[i] += partial_sum
            partial_sum = cnt[i]
        
        nums.sort()
        cnt.sort()
        
        ans = 0
        for i in range(n):
            ans = (ans + nums[i] * cnt[i]) % int(1e9 + 7)
        return ans
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        freq=[0]*len(nums)
        for a,b in requests:
            freq[a]+=1
            if b+1<len(nums): freq[b+1]-=1
        for i in range(1,len(nums)):
            freq[i]+=freq[i-1]
            
        freq.sort()
        nums.sort()
        ans=0
        for i in range(len(nums)):
            ans=(ans+freq[i]*nums[i])%((10**9)+7)
        return ans


MODULO = 10**9 + 7


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        events = [0] * len(nums)
        for s, e in requests:
            events[s] += 1
            if e + 1 < len(nums):
                events[e + 1] -= 1

        for i in range(1, len(events)):
            if events[i] == 0:
                events[i] = events[i-1]
            else:
                events[i] = events[i-1] + events[i]

        print(events)

        events.sort()
        nums.sort()

        summa = 0
        for v, n in zip(events, nums):
            summa = (summa + v * n) % MODULO
        return summa


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        times_requested = [0 for i in range(len(nums))]
        
        for request in requests:
            start, end = request[0], request[1]
            times_requested[end] += 1
            if start - 1 >= 0:
                times_requested[start - 1] -= 1
        
        curr_sum = 0
        for i in range(len(times_requested) - 1, -1, -1):
            curr_sum += times_requested[i]
            times_requested[i] = curr_sum
        
        times_requested.sort()
        nums.sort()
        ans = 0
        for i in range(len(nums) - 1, -1, -1):
            ans += times_requested[i] * nums[i]
            ans = ans % (10 ** 9 + 7)
        return ans
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        A = nums
        count = [0 for _ in range(n+1)]
        for r in requests:
            start = r[0]
            end = r[1]
            count[start] += 1
            count[end+1] -= 1
        
        for i in range(1, n+1):
            count[i] += count[i-1]
        # print(count)
        
        count = sorted(count, reverse=True)
        nums = sorted(nums, reverse=True)
        res = 0
        for i in range(len(count)):
            if count[i] == 0:
                break
            res += nums[i] * count[i]
        return res % (10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort()
        N = len(nums)
        bucket = [0] * N
        for a, b in requests:
            if a < N:
                bucket[a] += 1
            if b < N - 1:
                bucket[b+1] -= 1
        
        for i in range(1, N):
            bucket[i] = bucket[i-1] + bucket[i]
        bucket.sort()
        res = 0
        while bucket and bucket[-1] != 0 and nums[-1] != 0:
            res = (res + bucket[-1] * nums[-1]) % (10**9 + 7)
            bucket.pop()
            nums.pop()
        return res

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0] * (n+1)
        
        for r in requests:
            start, end = r
            count[start] += 1
            count[end+1] -= 1
        
        for i in range(1, n):
            count[i] = count[i-1] + count[i]
        
        nums.sort(reverse=True)
        count.sort(reverse=True)
        res = 0
        for num, c in zip(nums, count):
            if c == 0:
                break
            else:
                res += num * c
        return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort()
        N = len(nums)
        bucket = [0] * N
        for a, b in requests:
            if a < N:
                bucket[a] += 1
            if b < N - 1:
                bucket[b+1] -= 1
        
        for i in range(1, N):
            bucket[i] = bucket[i-1] + bucket[i]
        bucket.sort()
        res = 0
        while bucket and bucket[-1] != 0:
            res = (res + bucket[-1] * nums[-1]) % (10**9 + 7)
            bucket.pop()
            nums.pop()
        return res

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        diff = [0 for i in range(len(nums)+1)]
        
        for r in requests:
            diff[r[0]] += 1
            diff[r[1]+1] -= 1
        for i in range(1, len(diff)):
            diff[i] = diff[i-1] + diff[i]
        print(diff)
        diff.sort(reverse = True)
        nums.sort(reverse = True)
        answer = 0
        
        i = 0
        while diff[i] != 0:
            answer += diff[i]*nums[i]
            answer = answer % (1e9 + 7)
            i += 1
        return int(answer)
        


class Solution:
    def maxSumRangeQuery(self, nums, requests) -> int:
        chafen=[0]*(len(nums)+1)
        for req in requests:
            chafen[req[0]]+=1
            chafen[req[1]+1]-=1
        chafen=chafen[:-1]
        sum_count=[]
        lastsum=0
        for idx,cha in enumerate(chafen):
            lastsum+=cha
            sum_count.append(lastsum)
        sum_count=sorted(sum_count)
        nums=sorted(nums)
        res=0
        for idx in range(len(nums)):
            res+=sum_count[idx]*nums[idx]
            res%=1e9+7
        return int(res)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        start_end_count = [[0,0] for _ in nums]
        for start, end in requests:
            start_end_count[start][0] += 1
            start_end_count[end][1] += 1
        counts = [0 for _ in nums]
        count = 0
        for i, (sc, ec) in enumerate(start_end_count):
            count += sc
            counts[i] = count
            count -= ec
        return sum([a*b % 1000000007 for a, b in zip(sorted(counts), sorted(nums))]) % 1000000007 
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        if N == 0:
            return 0
        index_freq = [0 for i in range(N+1)]
        M = len(requests)
        for i in range(M):
            end = requests[i][1]
            start = requests[i][0]
            index_freq[start] += 1
            index_freq[end+1] -= 1
        total_freq = [0 for i in range(N)]
        total_freq[0] = index_freq[0]
        for i in range(1, N):
            total_freq[i] = index_freq[i] + total_freq[i-1]
        total_freq.sort(reverse = True)
        nums.sort(reverse = True)
        ret = 0
        for i in range(N):
            ret += nums[i] * total_freq[i]
        return ret % 1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        vals = []
        nums.sort()
        for i in range(len(nums)):
            vals.append(0)
        for request in requests:
            vals[request[0]] += 1
            if request[1] + 1 < len(nums):
                vals[request[1]+1] -= 1
        count = 0
        for i in range(len(vals)):
            vals[i] = vals[i]+count
            count = vals[i]
        vals.sort()
        index = len(nums)-1
        total = 0
        while vals[index] != 0 and index >= 0:
            total += vals[index]*nums[index]
            index -= 1
        return total%(10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        ans = 0
        
        freq = [0] * (n+1)
        for (a,b) in requests:
            freq[a] += 1
            freq[b + 1] -= 1
        for i in range(1,len(freq)):
            freq[i] += freq[i-1]
        freq.sort(reverse = True)
        nums.sort(reverse = True)
        return sum([freq[i]*nums[i] for i in range(n)])%MOD


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        diff = [0 for i in range(n+1)]
        for req in requests:
            diff[req[0]] += 1
            diff[req[1] + 1] -= 1
        for i in range(1, n+1): diff[i] += diff[i-1]
        diff.pop(-1)
        sort_idx = [i for i in range(n)]
        sort_idx = sorted(sort_idx, reverse = True, key = lambda x : diff[x])
        nums = sorted(nums, reverse = True)
        temp = [-1 for i in range(n)]
        for i in range(n): temp[sort_idx[i]] = nums[i]
        nums = temp[:]
        temp[0] = nums[0]
        ret = 0
        for i in range(1, n): temp[i] = temp[i-1] + nums[i]
        for req in requests:
            if (not req[0]): ret += temp[req[1]]
            else: ret += temp[req[1]] - temp[req[0] - 1]
            ret %= 1000000007
        return ret

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        freqs = [0] * (len(nums) + 1)
        for s, e in requests:
            freqs[s] += 1
            freqs[e + 1] -= 1
        freqs.pop()
        nzFreqs = []
        f = 0
        for i, (x, n) in enumerate(zip(freqs, nums)):
            f += x
            if f > 0:
                nzFreqs.append(f)
            nums[i] = -n
        heapq.heapify(nums)
        nzFreqs.sort(reverse=True)
        result = 0
        for f in nzFreqs:
            result += f * heapq.heappop(nums)
        return (-result) % 1000000007


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        \"\"\"
 
        \"\"\"
        import collections
        request_idx_mapping = collections.defaultdict(int)
        
        
        for open_idx, close_idx in requests:
            request_idx_mapping[open_idx] += 1
            request_idx_mapping[close_idx + 1] -= 1
        request_freq = [0 for _ in range(len(nums))]
        idxes = [i for i in range(len(nums))]
        current_requests = 0
        for idx in range(len(nums)):
            current_requests += request_idx_mapping[idx]
            
            request_freq[idx] = current_requests
        idxes.sort(key=lambda idx: request_freq[idx], reverse=True)
        nums.sort()
        
        result = 0
        
        for idx in idxes:
            freq = request_freq[idx]
            num = nums.pop()
            result += freq*num
        MOD = 10 ** 9 + 7
        return result % MOD
            

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        '''
        Discuss Solution thats faster at detecting
        the number of requests that overlap an index.
        
        Key Idea have array t, loop
        through requests [[start, end] ...]
        
        Make t[start] += 1 to indicate
        every index after start is counted once
        for this request overlap
        Make t[end + 1] -= 1 to indicate
        every index after end + 1 is counted one less
        for this request overlap
        
        The prefix sum of array t tells us
        the number of requests that overlap
        an index
        
        requests
        [[0,2],[1,3],[1,1]]
        
          -
          - - -
        - - -
        0 1 2 3 4 5
        1 2 3 4 5 9
        
        t
        0  1  2  3  4  5  6
        1  2 -1 -1 -1
        
        t_prefix
        0  1  2  3  4  5  6
        1  3  2  1  0  0  0
        
        t.pop to remove index 6
        Sort both nums and t and
        use zip to line them up
        This matches most frequently
        overlapped index with biggest
        num.
        
        nums
        1 2 3 4 5 9
        t
        0 0 1 1 2 3
        
        Multiply because index i gets overlapped
        t[i] times so the nums value of mapping
        also gets mulitplied that number of times
        for the sum
        
        nums[i] * t[i]
        0 0 3 4 10 27
        
        sum of final = 44
        '''
        t = [0] * (len(nums) + 1)
        
        for start, end in requests:
            t[start] += 1
            t[end + 1] -= 1
            
        for i in range(1, len(nums)):
            t[i] += t[i - 1]
        
        nums.sort()
        t.pop() # Makes it so t matches length with nums
        t.sort()

        return sum(a*b for a, b in zip(nums, t)) % (10**9 + 7)
            
        
            


import numpy as np
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
      freq = [0]*(len(nums)+1)
      for req in requests:
        freq[req[0]] += 1
        freq[req[1]+1] -= 1
      for i in range(1, len(freq)-1):
        freq[i] = freq[i] + freq[i-1]
      freq.sort(reverse = True)
      nums.sort(reverse = True)
      return sum([x*y for x,y in zip(freq[:-1], nums)]) % (10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        len_nums = len(nums)
        frequencies = [0] * (len_nums + 1)
        for start, end in requests:
            frequencies[start] += 1
            frequencies[end + 1] -= 1
        for k in range(1, len_nums):
            frequencies[k] += frequencies[k - 1]
        frequencies.sort(reverse=True)
        nums.sort(reverse=True)
        max_sum = 0
        for k in range(len_nums):
            max_sum += nums[k] * frequencies[k]
        return max_sum % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0] * (n + 1)
        for i, j in requests:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(nums)):
            res += v * c
        return res % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = 10**9+7
        starts = list(sorted([s for s, _ in requests]))
        ends = list(sorted([e for _, e in requests]))
        
        r = 0
        
        counts = []
        cur = 0
        si, ei = 0, 0
        for i in range(len(nums)):
            while si < len(starts) and starts[si] <= i:
                cur += 1
                si += 1
            while ei < len(ends) and ends[ei] < i:
                cur -= 1
                ei += 1
            counts.append(cur)
        
        sc = list(sorted(counts))
        sn = list(sorted(nums))
        
        # print(sc)
        # print(sn)
        
        for i in range(len(sc)):
            r += sc[i] * sn[i]        
        
        return r % MOD


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        l = [0] * (len(nums) + 1)
        for a, b in requests:
            l[a] += 1
            l[b + 1] -= 1
        return sum(m * a for m, a in zip(sorted(accumulate(l[:-1])), sorted(nums))) % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        M = 10**9+7
        
        n = len(nums)
        
        ## count: records the frequency that the range has been requested
        ## see reference: https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/
        count = [0] * (n+1)
        for req in requests:
            count[req[0]] += 1
            count[req[1]+1] -= 1
            
        ## sort count array by (frequencies, position_index)
        for i in range(1, n+1):
            count[i] += count[i-1]
        counts_ls = [(count[i], i) for i in range(n+1)]
        counts_ls.sort(key = lambda x: (-x[0], x[1]))
        
        ## the greatest number should have the greatest frequency
        ## so that the sum is maximized
        nums.sort(key = lambda x: -x)
        res = 0
        for i in range(n):
            res += nums[i] * counts_ls[i][0]
        return res % M

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        highest = sorted(nums, reverse=True)
        pointers = [[0,0] for _ in range(len(nums))]
        for req in requests:
            pointers[req[0]][0] += 1
            pointers[req[1]][1] += 1
        print(pointers)
        lefts = 0
        rights = 0
        freq = []
        for pointer in pointers:
            lefts += pointer[0]
            freq.append(lefts - rights)
            rights += pointer[1]
        ans = 0
        freq.sort(reverse=True)
        for i in range(len(freq)):
            
            ans += freq[i]*highest[i]
            
        mod = 10**9 + 7
        return ans % mod

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        M = 10**9+7
        
        n = len(nums)
        count = [0] * (n+1)
        for req in requests:
            count[req[0]] += 1
            count[req[1]+1] -= 1
            
        # print(count)
        for i in range(1, n+1):
            count[i] += count[i-1]
        # print(count)
        counts_ls = [(count[i], i) for i in range(n+1)]
        counts_ls.sort(key = lambda x: (-x[0], x[1]))
        # print(counts_ls)
        nums.sort(key = lambda x: -x)
        # print(nums)
        
        res = 0
        for i in range(n):
            res += nums[i] * counts_ls[i][0]
        return res % M

class Solution:
    def maxSumRangeQuery(self, A, req):
            n = len(A)
            count = [0] * (n + 1)
            for i, j in req:
                count[i] += 1
                count[j + 1] -= 1
            for i in range(1, n + 1):
                count[i] += count[i - 1]
            res = 0
            for v, c in zip(sorted(count[:-1]), sorted(A)):
                res += v * c
            return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:
        cnt = [0] * (len(a)+1)
        for s, e in r: 
            cnt[s] += 1; cnt[e+1] -= 1                    
        cnt = list(accumulate(cnt))                        
        return sum(x*y for x, y in zip(sorted(cnt[:-1]), sorted(a))) % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        ans = 0
        MOD = 10**9+7
        N=len(nums)
        walk = Counter()
        
        for s,e in requests:
            walk[s]+=1
            walk[e+1]-=1
        
        vals = []
        amt = 0
        for val in range(0,N):
            amt += walk[val]
            vals.append(amt)
        
        nums.sort()
        vals.sort()
        ans = 0
        for v1,v2 in zip(nums, vals):
            ans += v1*v2
        
        return ans % MOD

\"\"\"
0 1 2 3 4 5 6
X X X X X X X
  + + +
+ +
      + + + +

X X X X X X X
1 2 1 2 1 1 1


-1 0 1 2 3 4 5 6
   X X X X X X X
   + + + + + + +   

diff[i] : freq[i] - freq[i-1]
freq[i-1] + diff[i] = freq[i]

[1-3] [2-5]
0  1  2  3  4  5 
  +1       -1
     +1        -1 

---------------------
0  1  1  0  -1  -1  diff 
0  1  2  2   1   0

\"\"\"



class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0] * (n + 1)
        for i, j in requests:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(nums)):
            res += v * c
        return res % (10**9 + 7)
        
        
        
        
        
        
        
        
        

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mod = 10**9 + 7
        rank = [0] * (len(nums) + 1)
        for i, j in requests:
            rank[i] += 1
            rank[j + 1] -= 1
        for i in range(1, len(nums)):
            rank[i] = rank[i - 1] + rank[i]
        
        rank = rank[:-1]
        nums.sort()
        rank.sort()
        total = 0
        for i, j in zip(nums,rank):
            total += i * j
        return total % mod

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums = sorted(nums, reverse=True)
        n = len(nums)
        count = [0] * (n+1)
        for i,j in requests:
            count[i] +=1
            count[j+1] -=1
        for i in range(1, n):
            count[i] += count[i-1]
        counts = sorted(count, reverse=True)
        res = 0
        for i in range(n):
            res+=nums[i]*counts[i]
        return res % (10**9+7)


class Solution:
    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:
        n = len(A)
        count = [0] * (n+1)
        
        for i, j in req:
            count[i] += 1
            count[j+1] -= 1
            
        for i in range(1, n+1):
            count [i] += count[i-1]
        
        res = 0
        A.sort()
        count.pop()
        count.sort()
        
        for v, c in zip(count, A):
            res += v * c
            
        return res % (pow(10, 9) + 7)
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # n = len(A)
        # count = [0] * (n + 1)
        # for i, j in req:
        #     count[i] += 1
        #     count[j + 1] -= 1
        # for i in range(1, n + 1):
        #     count[i] += count[i - 1]
        # res = 0
        # for v, c in zip(sorted(count[:-1]), sorted(A)):
        #     res += v * c
        # return res % (10**9 + 7)


from itertools import accumulate
from operator import mul
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        cums = [0 for i in range(len(nums)+1)]
        for start,end in requests:
            cums[start]+=1
            cums[end+1]-=1
        return sum( map(mul,sorted(accumulate(cums),reverse=True),sorted(nums,reverse=True) ))%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        MOD = (10**9+7)
        n = len(nums)
        ranks = [0]*(n+1)
        for start,end in requests:
            ranks[start] += 1
            ranks[end+1] -= 1
        for i in range(1,n+1):
            ranks[i] += ranks[i-1]
        ranks = ranks[:n]
        ranks.sort()
        nums.sort()
        ans = 0
        for i in range(len(ranks)):
            ans += ranks[i]*nums[i]
        return ans % MOD

class Solution:
    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:
        n = len(A)
        count = [0] * (n + 1)
        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(A)):
            res += v * c
        return res % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, A, req):
        n = len(A)
        count = [0] * (n + 1)
        for i, j in req:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(A)):
            res += v * c
        return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        occurances = [0] * len(nums)
        for request in requests:
            occurances[request[0]] += 1
            if (request[1] + 1 < len(nums)):
                occurances[request[1] + 1] -= 1
        for i in range(1, len(nums)):
            occurances[i] += occurances[i - 1]
        mod = int(1e9+7)
        occurances.sort()
        nums.sort()
        res = 0
        for i in range(len(nums)):
            res = (res + nums[i] * occurances[i]) % mod
        return res

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        # We want to calculate the frequency for A[i].
        # Assign the big element A[i] to the position queried more frequently.
        n = len(nums)
        count = [0] * (n + 1)
        
        for i, j in requests:
            count[i] += 1
            count[j + 1] -= 1
            
        for i in range(1, n + 1):
            count[i] += count[i - 1]
            
        res = 0
        for v, c in zip(sorted(count[:-1]), sorted(nums)):
            res += v * c
            
        return res % (10**9 + 7)
    
    


class Solution:
    def maxSumRangeQuery(self, nums, requests) -> int:
        \"\"\"
        Given an array of integers (nums) and an array of range
        requests (requests), each request containing the start
        and end indexes of a range within nums, this program
        determines the maximum sum over requests for all permutations
        of nums.

        :param nums: array of integers
        :type nums: list[int]
        :param requests: array of range requests, each containing
                         the start and end indexes of a range of
                         indexes within nums
        :type requests: list[list[int]]
        :return: maximum sum over the range requests (requests)
        :rtype: int
        \"\"\"

        \"\"\"
        Initialize length of nums array (len_nums)
        \"\"\"
        len_nums = len(nums)

        \"\"\"
        Determine the frequency for each index within nums
        \"\"\"
        frequencies = [0] * (len_nums + 1)
        for start, end in requests:
            frequencies[start] += 1
            frequencies[end + 1] -= 1
        for k in range(1, len_nums):
            frequencies[k] += frequencies[k - 1]

        \"\"\"
        Determine the maximum range sum (max_sum).
        \"\"\"
        frequencies.sort(reverse=True)
        nums.sort(reverse=True)
        max_sum = 0
        for num, frequency in zip(nums, frequencies):
            max_sum += num * frequency
        return max_sum % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        temp = [0]*(n+1)
        
        for ind,i in enumerate(requests):
            s = i[0]; e = i[1]
            temp[s]+=1
            temp[e+1]-=1
            
        for i in range(1,n+1):
            temp[i] += temp[i-1]
            
        temp = sorted(temp,reverse = 1)
        nums = sorted(nums,reverse = 1)
    
        ans = 0
        for i in range(n):
            ans += nums[i]*temp[i]
        
        return ans%((10**9)+7)

from collections import Counter, deque
from itertools import chain

import heapq

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        f = [0] * (len(nums) + 1)
        for i, j in requests:
            f[i] += 1
            f[j+1] -= 1
        for i in range(1, len(nums) + 1):
            f[i] += f[i - 1]
        return sum(x * y for x, y in zip(sorted(f, reverse=True), sorted(nums, reverse=True))) % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        t = [0]*(n + 1)
        for a, b in requests:
            t[a] += 1
            t[b + 1] -= 1
        for i in range(1, n):
            t[i] += t[i - 1]
        
        nums.sort()
        t.pop()
        t.sort()

        return sum(a*b for a, b in zip(nums, t)) % mod

from collections import Counter, deque
from itertools import chain

import heapq

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        f = [0] * (len(nums) + 1)
        for i, j in requests:
            f[i] += 1
            f[j+1] -= 1
        for i in range(1, len(nums) + 1):
            f[i] += f[i - 1]
        
        f.sort(reverse=True)
        nums.sort(reverse=True)
        return sum(x * y for x, y in zip(f, nums)) % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, A, qs):
        A.sort(reverse=1)
        n=len(A)
        r=[0]*(n+1)
        for a,b in qs:
            r[a]+=1
            r[b+1]-=1
        for i in range(1,n):
            r[i]+=r[i-1]
        r.pop()
        r.sort(reverse=1)
        ans=0
        for i,k in enumerate(r):
            ans+=A[i]*k
        return ans%(10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        index_count = [0]* (len(nums)+1)
        for request in requests:
            index_count[request[0]]+= 1
            index_count[request[1]+1]-= 1
            
        for i in range(1, len(index_count)):
            index_count[i] += index_count[i-1]
        nums.sort(reverse = True)
        index_count.sort(reverse=True)
       
        res = sum(i* v for i,v in zip(nums, index_count))
        return res %( 10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0]*(n+1)
        for i in range(len(requests)):
            start = requests[i][0]
            end = requests[i][1]
            count[start]+=1
            count[end+1]-=1
        for i in range(1,n):
            count[i]+=count[i-1]
        #print(count)
        x=count.pop()
        nums.sort(reverse=True)
        count.sort(reverse=True)
        #print(nums)
        #print(count)
        ans = 0
        for i in range(n):
            ans+=(count[i]*nums[i])%(10**9+7)
        
        return ans%(10**9+7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        len_nums = len(nums)

        \"\"\"
        Determine the frequency for each index within nums
        \"\"\"
        frequencies = [0] * (len_nums + 1)
        for start, end in requests:
            frequencies[start] += 1
            frequencies[end + 1] -= 1
        for k in range(1, len_nums):
            frequencies[k] += frequencies[k - 1]

        \"\"\"
        Determine the maximum range sum (max_sum).
        \"\"\"
        frequencies.sort(reverse=True)
        nums.sort(reverse=True)
        max_sum = 0
        for num, frequency in zip(nums, frequencies):
            max_sum += num * frequency
        return max_sum % (10**9 + 7)

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)
            


import heapq

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # build heat map
        # put highest numbers in hottest spots
        heatMap = [0 for i in range(len(nums)+1)]
        for req in requests:
            heatMap[req[0]] += 1
            heatMap[req[1]+1] -= 1 
            # for i in range(req[0], req[1]+1):
            #     heatMap[i] += 1
        for i in range(1,len(heatMap)):
            heatMap[i] += heatMap[i-1]
        heatMap.sort(reverse=True)
        # heap of non-zero size heatMap
        nums.sort(reverse=True)
        numIndex = 0
        total = 0
        for count in heatMap:
            if count == 0:
                break
            total += nums[numIndex] * count
            numIndex += 1
        return total % (10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        total = 0
        prefix = [0] * len(nums)
        for x, y in requests:
            prefix[x] += 1
            if y < len(prefix) - 1:
                prefix[y + 1] -= 1
        for i in range(len(prefix) - 1):
            prefix[i+1] += prefix[i]
        nums.sort(reverse=True)
        prefix.sort(reverse=True)
        for i in range(len(nums)):
            total += (nums[i] * prefix[i])
        total %= (10 ** 9 + 7)
        return total


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        pref = [0] * n
        for req in requests:
            l, r = req
            pref[l] += 1
            if r + 1 < n: pref[r + 1] -= 1
        
        for i in range(1, n):
            pref[i] += pref[i - 1]
        
        
        pref.sort()
        nums.sort()
        
        ans = 0
        MOD = 10 ** 9 + 7
        
        for i in range(n):
            ans = (ans + nums[i] * pref[i]) % (MOD)
        
        return ans
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        # calculate position count
        # permutation by sorting
        reqs = [0] * (len(nums) + 1)   # idx, +1/-1
        for request in requests:
            reqs[request[0]] += 1
            reqs[request[1] + 1] -= 1
        prev = 0
        reqs.pop()
        for i in range(len(reqs)):
            reqs[i] += prev
            prev = reqs[i]
        
        #print(reqs)
        nums.sort(reverse = True)
        reqs.sort(reverse = True)
        
        ret = 0
        M = pow(10, 9) + 7
        for i in range(len(nums)):
            ret = (ret + nums[i] * reqs[i]) % M
        
        return ret


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n, m = len(nums), len(requests)
        count = [0 for _ in range(n + 1)]
        for begin, end in requests:  
            count[begin] += 1
            count[end + 1] -= 1
        for i, c in enumerate(count):
            if i != 0:
                count[i] += count[i-1]
        nums.sort(reverse=True)
        count.sort(reverse=True)
        total = 0
        for num, count in zip(nums,count):
            total += (num * count)
        return total % (10**9 + 7)
        
        
        
\"\"\"
  1 2 3
0,1

\"\"\"

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        calls = [0] * (len(nums) + 1)
        for start, end in requests:
            calls[start] += 1
            calls[end+1] -= 1 
        for i in range(1, len(calls)):
            calls[i] += calls[i-1]
        calls.sort(reverse=True)
        nums.sort(reverse=True)
        return sum([i * j for i, j in zip(calls[:-1], nums)])%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        occurances = [0] * len(nums)
        for request in requests:
            occurances[request[0]] += 1
            if (request[1] + 1 < len(nums)):
                occurances[request[1] + 1] -= 1
        for i in range(1, len(nums)):
            occurances[i] += occurances[i - 1]
        mod = int(1e9+7)
        occurances.sort()
        nums.sort()
        res = 0
        for (x, y) in zip(occurances, nums):
            res = (res + x * y) % mod
        return res

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N=len(nums)
        add=(N+1)*[0]
        ded=(N+1)*[0]
        M=len(requests)
        for start,end in requests:
            add[end+1]+=1
            ded[start]+=1
        dp=N*[0]
        z1=0
        z2=0
        for i in range(N):
            z1+=add[i]
            z2+=ded[i]
            dp[i]=z2-z1
        nums.sort()
        dp.sort()
        return sum(nums[i]*dp[i] for i in range(N))%(10**9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        total = 0
        prefix = [0] * len(nums)
        
        for x, y in requests:
            prefix[x] += 1
            if y < len(prefix) - 1:
                prefix[y + 1] -= 1
                
        for i in range(len(prefix) - 1):
            prefix[i+1] += prefix[i]
        
        nums.sort(reverse=True)
        prefix.sort(reverse=True)
        for i in range(len(nums)):
            total += (nums[i] * prefix[i])
        total %= (10 ** 9 + 7)
        return total


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        res = 0
        MOD = 10**9 + 7
        ln = len(nums)
        c = [0]*(ln+1)
        for r in requests:
          c[r[0]] += 1
          c[r[1]+1] -= 1
        for i in range(1, ln):
          c[i] += c[i-1]
        
        
        #c = sorted([(i, v) for i, v in enumerate(c)], key=lambda x: -x[-1])
        # print (c)
        nums = sorted(nums, key=lambda x:-x)      # nlogn
        ctr = collections.defaultdict(lambda : 0)
        for cv in c:
          ctr[cv] += 1
        # print (ctr)
        
        j = 0
        for i in range(len(requests), 0, -1):
          # print (ctr[i])
          m = ctr[i]
          while m:
            res += (nums[j]*i)%MOD
            j += 1
            m -= 1
            res = res%MOD
          
        return res%MOD
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        arr=[0]*(len(nums)+1)
        for s,e in requests:
            arr[s]+=1
            arr[e+1]-=1
        for i in range(1,len(arr)):
            arr[i]+=arr[i-1]
        arr.pop()
        arr.sort()
        res=0
        for i,v in enumerate(sorted(nums)):
            res+=v*arr[i]
            res%=(10**9+7)
        return res

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n, m = len(nums), len(requests)
        count = [0 for _ in range(n + 1)]
        for begin, end in requests:  
            count[begin] += 1
            count[end + 1] -= 1
        for i, c in enumerate(count):
            if i != 0:
                count[i] += count[i-1]
        nums.sort(reverse=True)
        count.sort(reverse=True)
        total = 0
        for num, count in zip(nums,count):
            if count == 0: break
            total += (num * count)
        return total % (10**9 + 7)
        
        
        
\"\"\"
  1 2 3
0,1

\"\"\"

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        q = [] ; ans = 0 ; L_n = len(nums) ; L_r = len(requests)
        for i in range(L_n):
            q.append(0)
        for i in range(L_r) :
            q[requests[i][0]] += 1
            now = requests[i][1]+1
            if now < len(q):
                q[now] -= 1 
        for i in range(1,L_n) :
            q[i] += q[i-1]
        q.sort(reverse=True) ; nums.sort(reverse=True)
        for i in range(L_n):
            if q[i] == 0 : 
                q = q[0:i]
                break
        for i in range(len(q)) :
            ans += q[i] * nums[i]
            ans = ans %(10**9 + 7 )
        return ans

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums.sort(reverse=True)
        ans = 0
        MOD = 10 ** 9 + 7
        cnt = [0] * (len(nums) + 1)
        for r in requests:
            cnt[r[0]] += 1
            cnt[r[-1] + 1] -= 1 
        for i in range(1, len(nums)):
            cnt[i] += cnt[i - 1]
        cnt = cnt[:-1]
        v = sorted(enumerate(cnt), key=operator.itemgetter(1), reverse=True)
        j = 0
        for _, k in v:
            ans += nums[j] * k
            j += 1
        return ans % MOD

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        counts = [0] * (len(nums) + 1)
        for start, end in requests:
            counts[start] += 1
            counts[end + 1] -= 1
        for i in range(1, len(nums)):
            counts[i] += counts[i - 1]
        counts.sort(reverse = True)
        nums.sort(reverse = True)
        return sum(c * n for c, n in zip(counts, nums)) % (10 ** 9 + 7)


from heapq import heappush,heappop
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0]*(n+1)
        for request in requests:
            start,end = request
            # amazing way to find frequency at each index without looping
            # from start to end
            count[start]+=1
            count[end+1]-=1
        
        for i in range(1,n+1):
            # using prefix sum
            count[i]+=count[i-1]
        answer = 0
        nums.sort()
        c = count[:-1]
        c.sort()
        for a,b in zip(nums,c):
            answer += a*b
        
        mod = (10**9)+7
        return answer%mod
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        nums = sorted(nums)
        n = len(nums)
        freq = [0] * (n+1)
        for l, r in requests:
            freq[l] += 1
            freq[r+1] -= 1
        for i in range(1, n):
            freq[i] += freq[i-1]
        freq = sorted(freq[:n])
        return sum(freq[i] * nums[i] for i in range(n)) % 1000000007

class Solution:
    def maxSumRangeQuery(self, nums: List[int], reqs: List[List[int]]) -> int:
        MOD = int(1e9)+7
        n = len(nums)
        weights = [0 for _ in range(n)]
        
        for x,y in reqs:
            weights[x]+=1
            if y<n-1:
                weights[y+1]-=1
        
        for i in range(1,n):
            weights[i] += weights[i-1]
        
        print(weights)
        
        weights.sort(reverse = True)
        nums.sort(reverse = True)
        ans = 0
        
        for i in range(n):
            ans += weights[i]*nums[i]
            
        return ans % MOD
            
        


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        
        frequency = [0 for i in range(len(nums))]
        
        
        for u, v in requests:
            
            frequency[u] += 1
            if v + 1 < len(nums): frequency[v + 1] -= 1
                
        for i in range(1, len(frequency)):
            
            frequency[i] += frequency[i - 1]
            
        frequency.sort()
        nums.sort()
        
        Sum = 0
        while nums:
            
            Sum += nums.pop()*frequency.pop()
            
        return Sum%(10**9 + 7)
            
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        count = [0] * (n + 1)
        for i, j in requests:
            count[i] += 1
            count[j + 1] -= 1
        for i in range(1, n + 1):
            count[i] += count[i - 1]
        # print(count)
        count.sort(reverse = True)
        res = 0
        nums.sort()
        for i in range(n):
            if count[i] == 0:
                break
            res += count[i] * nums.pop()
        return res % (10 ** 9+7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        #sort the array nums
        nums.sort(reverse = True)
        N, M = len(nums), len(requests)
        freq = [0 for i in range(N+1)]
        res = 0

        for start, end in requests:
            freq[start] += 1
            freq[end + 1] -= 1
        for i in range(1, N+1):
            freq[i] += freq[i-1]
        freq.sort(reverse = True)
        for i in range(N):         
            res += freq[i] * nums[i]
            if freq[i] == 0 or nums[1] == 0:
                break
        return res%(10**9 + 7)


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        n = len(nums)
        ind = [0] * (n+1)
        
        for i,j in requests:
            ind[i] += 1
            ind[j+1] -= 1
        
        for i in range(1, n):
            ind[i] += ind[i-1]
        
        ind = sorted(list(zip(ind,range(n))))
        nums = sorted(nums)
        
        res = 0
        while ind:
            x,y = ind.pop()
            if x == 0:
                return res % (10**9 + 7)
            res += x*nums.pop()
        
        return res % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        ''' https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854153/Simple-solution-Python-O(n)
            Find most requested position and calculate sum request_count * element(order of request_count) .
        '''
        mod = 10**9+7
        n = len(nums)
        arr = [0] * (n+1) # add extra element for handel n+1 case
        for i, j in requests:
            arr[i] += 1
            arr[j+1] -= 1
        for i in range(1, n+1):
            arr[i] += arr[i-1]
        arr = arr[:n] # remove the extra element
        nums.sort()
        arr.sort()
        ans = 0
        for i in range(n):
            ans += nums[i] * arr[i]
        return ans%mod

from collections import Counter
class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
                
        # 1a. Find optimal permutation of nums. O(N^2) / O(requests * len(requests))
            # Create Counter with number of entries for each number. 
            # Sort # of requests from large to small
        # c = {i : 0 for i, v in enumerate(nums)}
        # for r in requests:
        #     for i in range(r[0], r[1] + 1):
        #         c[i] += 1
        # requests_per_num = [c[k] for k in c]
        # requests_per_num.sort(reverse=True) 
        
        # 1b. Let's try to do this in O(N) + O(R) time. 
        # Create Counters of start / end values of requests.
        start = Counter([r[0] for r in requests])
        end = Counter([r[1] for r in requests])

        # Loop through possible nums.
        running_sum = 0
        requests_per_num = []
        
        # Use counter to update num requests. 
        for i, n in enumerate(nums):
            running_sum += start[i]
            running_sum -= end[i - 1]
            requests_per_num.append(running_sum)
        requests_per_num.sort(reverse=True) 
            
        # 2. Order numbers to match most common requests.
        nums_copy = [n for n in nums]
        nums_copy.sort(reverse=True)
        
        # Compute sum.
        max_sum = 0
        for n, r in zip(nums_copy, requests_per_num):
            max_sum += n * r
            
        # Return max sum mod 10 ** 9 + 7
        return max_sum % (10 ** 9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        frequency = [0 for i in range(len(nums))]
        for request in requests:
            start,end = request
            frequency[start] += 1
            if end+1 < len(frequency):
                frequency[end+1] -= 1
        
        indexToFrequency = []
        for i in range(0,len(frequency)):
            if i != 0:
                frequency[i] += frequency[i-1]
            indexToFrequency.append((frequency[i],i))
        indexToFrequency.sort(reverse = True)
        nums.sort(reverse = True)
        
        numbers = [0 for _ in range(len(nums))]
        for i in range(len(indexToFrequency)):
            _,index = indexToFrequency[i]
            numbers[index] = nums[i]
        
        prefixSum = list(numbers)
        for i in range(1,len(numbers)):
            prefixSum[i] += prefixSum[i-1]
            prefixSum[i] %= (10 ** 9 + 7)
            
        result = 0
        for request in requests:
            start,end = request
            if start == 0:
                result += prefixSum[end]
            else:
                result += (prefixSum[end]-prefixSum[start-1])
            result = result % (10 ** 9 + 7)
        return result
        
        
        
        
        
        
            


class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        indmap = {ind:0 for ind in range(len(nums))}
        for r in requests:
            indmap[r[0]] += 1
            if r[1]+1 < len(nums):
                indmap[r[1]+1] -=1
        for i in range(1, len(nums)):
            indmap[i] += indmap[i-1]
        
        indices_sorted_by_occ = sorted(indmap.keys(), key= lambda ind: indmap[ind], reverse=True)
        sorted_freqs = [indmap[ind] for ind in indices_sorted_by_occ]
                
        sorted_nums = sorted(nums, reverse = True)
        sol = sum(n*f for n, f in zip(sorted_nums, sorted_freqs))
        
        return sol % (10**9 + 7)

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        i_count = [0] * N

        for start, end in requests:
            i_count[start] += 1

            if end + 1 < N:
                i_count[end + 1] -= 1

        for i in range(1, N):
            i_count[i] += i_count[i - 1]

        s = 0
        m = 1000000007
        i_count.sort()
        nums.sort()
        for i in range(N):
            s += i_count[i] * nums[i]

        return s % m