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:\n  def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n    count = [0] * (len(nums) + 1)\n    for start, end in requests:\n      count[start] += 1\n      count[end + 1] -= 1\n    for i in range(1, len(nums) + 1):\n      count[i] += count[i - 1]\n    count.pop()\n\n    res = 0\n    for n, times in zip(sorted(nums), sorted(count)):\n      res += n * times\n\n    return res % (10 ** 9 + 7)\n    \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        count_lst = [0]*(len(nums) + 1)\n        for start, end in requests:\n            count_lst[start] += 1\n            count_lst[end + 1] -= 1\n        # print(count_lst)    \n        ret_lst = [0]*(len(nums) + 1)\n        for i in range(len(ret_lst)):\n            if i == 0 and count_lst[i] != 0:\n                ret_lst[i] = count_lst[i]\n                continue\n            \n            ret_lst[i] = ret_lst[i - 1] + count_lst[i]\n        # print(ret_lst)\n        ret_lst.sort(reverse = True)\n        nums.sort(reverse = True)\n        ret_num = 0\n        \n        for i in range(len(nums)):\n            ret_num += ret_lst[i]*nums[i]\n        return ret_num % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        lenn = len(nums)\n        ranks = [0] * (lenn + 1)\n        for i, j in requests:\n            ranks[i]  += 1\n            ranks[j+1] -= 1\n        for i in range(1, lenn + 1):\n            ranks[i] += ranks[i-1]\n        ranks = ranks[:lenn]\n        return sum(x*y for x, y in zip(sorted(ranks), sorted(nums))) % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:\n        n = len(A)\n        count = [0] * (n + 1)\n        \n        for i,j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n            \n        for i in range(1,n + 1):\n            count[i] += count[i - 1]\n        res= 0\n        \n        for v,c in zip(sorted(count[:-1]),sorted(A)):\n            res += v * c\n        return res % (10 ** 9 + 7)", "from collections import defaultdict\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        count = [0] * len(nums)\n        for pair in requests:\n            count[pair[0]] += 1\n            if pair[1] != len(nums) - 1:\n                count[pair[1] + 1] -= 1\n        dct = defaultdict(int)\n        curr = 0\n        total = 0\n        for i in range(len(nums)):\n            curr += count[i]\n            if not curr:\n                continue\n            dct[curr] += 1\n            total += 1\n        nums.sort()\n        res = 0\n        items = sorted(list(dct.items()), reverse = True)\n        for key, val in items:\n            for i in range(val):\n                res += key * nums[-1]\n                nums.pop()\n        return res % (10 ** 9 + 7)\n        \n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        interval = defaultdict(int)\n        Qs = []\n        Qe = []\n        for [i,j] in requests:\n            heapq.heappush(Qs, i)\n            heapq.heappush(Qe, j+1)\n        count = 0\n        for i in range(len(nums)):\n            while Qs and Qs[0] <= i:\n                heapq.heappop(Qs)\n                count += 1\n            while Qe and Qe[0] <= i:\n                heapq.heappop(Qe)\n                count -= 1\n            interval[i] = count\n        #print(interval)\n        keys = sorted(interval, key = lambda x: interval[x], reverse = True)\n        #print(keys)\n        values = sorted(nums, reverse = True)\n        finala = [0 for i in range(len(nums))]\n        j = 0\n        for i in keys:\n            finala[i] = values[j]\n            j += 1\n        #print(finala)\n        #print(keys)\n        fsum = 0\n        for i in keys:\n            fsum += finala[i] * interval[i]\n        return fsum % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        requests.sort(reverse = True)\n        counts = []\n        ends = []\n        curr = 0\n        for i in range(N):\n            while requests and requests[-1][0] == i:\n                s, e = requests.pop()\n                curr += 1\n                heapq.heappush(ends, e)\n            counts.append(curr)\n            while ends and ends[0] == i:\n                heapq.heappop(ends)\n                curr -= 1\n                \n        res = 0\n        for v, c in zip(sorted(counts), sorted(nums)):\n            res += v * c\n        return res % (10**9+7)\n", "from heapq import *\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = (10**9 + 7)\n        nums.sort(reverse=True)\n        \n        j = 0\n        s = 0\n        cnts = []\n        n = len(nums)\n        count = [0] * (n + 1)\n        for i, j in requests:\n            count[i] += 1\n            count[j + 1] -= 1\n            \n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n\n        count.sort(reverse=True)\n        \n        s = 0\n        for i in range(len(nums)):\n            if count[i] > 0:\n                s += count[i] * nums[i]\n            else:\n                break\n\n        return s % MOD", "\nclass Solution:\n    def maxSumRangeQuery(self, A, req):\n        n = len(A)\n        count = [0] * (n + 1)\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(A)):\n            res += v * c\n        return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        ans = [0]*(n+1)\n        for i,j in requests:\n            ans[i] += 1\n            ans[j+1] -= 1\n        for i in range(1,n):\n            ans[i] += ans[i-1]\n        ans.pop()\n        result = 0\n        for count, value in zip(sorted(ans),sorted(nums)):\n            result += count*value\n        return result % (10**9+7)\n        \n", "from collections import Counter\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        stCount = Counter([request[0] for request in requests])\n        endCount = Counter([request[1] for request in requests])\n        tmp = []\n        for st, times in stCount.items():\n            tmp.append([st, 's', times])\n        for end, times in endCount.items():\n            tmp.append([end, 'z', times])\n        nums.sort(reverse=True)\n        tmp.sort()\n        \n        segments = []\n        \n        \n        times = 0\n        prev = 0\n        MOD = (10 ** 9) + 7\n        for point in tmp:\n            if point[1] == 's':\n                segments.append([point[0] - prev, times])\n                times += point[2]\n                prev = point[0]\n            if point[1] == 'z':\n                segments.append([point[0] - prev + 1, times])\n                times -= point[2]\n                prev = point[0] + 1\n        \n            # prev = point[0]\n        segments.sort(key=lambda element:element[1], reverse=True)\n        st = 0\n        ans = 0\n       \n        for segment, times in segments:\n            for i in range(st, st + segment):\n                ans += nums[i] * times\n            ans %= MOD\n            st = st + segment\n            \n        \n        \n            \n        return ans", "class Solution:\n    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:\n            cnt = [0] * (len(a)+1)\n            for s, e in r: \n                cnt[s] += 1; cnt[e+1] -= 1                    \n            cnt = list(accumulate(cnt))                        \n            return sum(x*y for x, y in zip(sorted(cnt[:-1]), sorted(a))) % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        bucket = [0] * N\n        for a, b in requests:\n            if a < N:\n                bucket[a] += 1\n                if b < N - 1:\n                    bucket[b+1] -= 1\n        bucket = list(itertools.accumulate(bucket))\n        # for i in range(1, N):\n            # bucket[i] = bucket[i-1] + bucket[i]\n        nums.sort()\n        bucket.sort()\n        return sum(x * y for x, y in zip(nums, bucket)) % (10 ** 9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        a = [0 for i in range(len(nums)+1) ]\n        for i in requests :\n            a[i[0]] += 1\n            a[i[1]+1] -= 1\n\n        for i in range(1,len(a)):\n            a[i] = a[i] + a[i-1]\n            \n\n        a.pop(-1)\n        \n\n        nums = sorted(nums,reverse=True)\n\n        pair = [[0,number,index] for index , number in enumerate(a)]\n        pair = sorted(pair,key=lambda word: (-word[1]))\n\n        for i in range(len(nums)):\n            pair[i][0] = nums[i]\n        \n\n        maxSum = 0\n\n        for i in pair :\n            maxSum += i[0] * i[1]\n\n\n\n        return maxSum % ((10 ** 9) + 7)", "\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], query: List[List[int]]) -> int:\n        nums = sorted(nums)\n        n = len(nums)\n        freq = [0] * (n+1)\n        for l, r in query:\n            freq[l] += 1\n            freq[r+1] -= 1\n        for i in range(1, n):\n            freq[i] += freq[i-1]\n        freq = sorted(freq[:n])\n        return sum(freq[i] * nums[i] for i in range(n)) % 1000000007", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        frequencies = [0] * len(nums)\n        \n        for start, end in requests:\n            frequencies[start] += 1\n            if end+1 < len(frequencies): frequencies[end + 1] -= 1\n\n        for i in range(1, len(frequencies)):\n            frequencies[i] = frequencies[i] + frequencies[i - 1]\n        \n        nums.sort(reverse=True)\n        frequencies.sort(reverse=True)\n        \n        maxSum = 0\n        for i in range(len(nums)):\n            maxSum += nums[i] * frequencies[i]\n            \n        return maxSum % (10**9 + 7)\n    \n    \n    \n\\\"\\\"\\\"\ndef maxSumRangeQuery(self, A, req):\n        n = len(A)\n        count = [0] * (n + 1)\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in xrange(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(A)):\n            res += v * c\n        return res % (10**9 + 7)\n\\\"\\\"\\\"", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        l = len(nums)\n        if l == 0: return 0\n        acc = [0] * (l + 1)\n        for r in requests:\n            acc[r[0]] += 1\n            acc[r[1] + 1] -= 1\n        app = [0] * (l)\n        app[0] = acc[0]\n        for i in range(1, l):\n            app[i] = app[i - 1] + acc[i]\n        app.sort()\n        nums.sort()\n        return sum([app[i] * nums[i] for i in range(l)]) % (10 ** 9 + 7)", "from collections import deque\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        freq_arr = [0]*n\n        requests.sort()\n        starts = deque([request[0] for request in requests])\n        requests.sort(key=lambda x: x[1])\n        ends =  deque([request[1] for request in requests])\n        active_intervals = 0\n        for pos in range(n):\n            while(starts and pos==starts[0]):\n                        starts.popleft()\n                        active_intervals += 1\n            while(ends and pos==ends[0]+1):\n                        ends.popleft()\n                        active_intervals -= 1            \n            freq_arr[pos] = active_intervals\n        \n        \n        nums.sort(reverse=True)\n        freq_arr.sort(reverse=True)\n        answer = 0\n        for n,f in zip(nums,freq_arr):\n            answer += n*f\n        return answer % ((10**9) + 7)\n        \n                \n                \n                \n                \n        \n\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        '''\n        requests can be converted to a frequency for each spot.\n        Then the highest frequency spot should get the largest item, \n        and continue to the next largest item.\n        '''\n        s = sorted([a for a, _ in requests])\n        e = sorted([a for _, a in requests])\n\\t\\t\n        freq = [bisect_right(s, i) - bisect_left(e, i) for i in range(len(nums))]\n\\t\\t\\t\n        res = sum(f * n for f, n in zip(sorted(freq), sorted(nums)))\n        return res % int(1e9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        ans = [0]*(n+1)\n        for i,j in requests:\n            ans[i] += 1\n            ans[j+1] -= 1\n        for i in range(1,n):\n            ans[i] += ans[i-1]\n        ans.pop()\n        result = 0\n        for count, value in zip(sorted(ans, reverse = True),sorted(nums, reverse = True)):\n            result += count*value\n        return result % (10**9+7)\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        i_count = [0] * N\n\n        for start, end in requests:\n            i_count[start] += 1\n\n            if end + 1 < N:\n                i_count[end + 1] -= 1\n\n        for i in range(1, N):\n            i_count[i] += i_count[i - 1]\n\n        s = 0\n        m = 1000000007\n        i_count.sort()\n        nums.sort()\n        for i in range(N):\n            s += i_count[i] * nums[i]\n            if s > m:\n                s %= m\n\n        return s", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        prefSum = [0 for x in range(len(nums))]\n        starts = sorted([x[0] for x in requests])\n        ends = sorted([x[1] for x in requests])\n        \n        count = 0\n        s = 0\n        e = 0\n        for i in range(len(nums)):\n            while s < len(starts) and starts[s] == i:\n                count += 1\n                s += 1\n            \n            while e < len(ends) and ends[e] < i:\n                count -= 1\n                e += 1\n            \n            prefSum[i] = count\n        \n        prefSum.sort()\n        nums.sort()\n        \n        res = 0\n        for i in range(len(nums)):\n            res += prefSum[i] * nums[i]\n            \n        mod = int(1e9 + 7)\n        \n        return res % mod", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        events = []\n        for s, e in requests:\n            events.append((s, 1))\n            events.append((e + 1, -1))\n        events.sort()\n        n = len(nums)\n        request_count = [0] * n\n        count = 0\n        i = 0\n        for j in range(n):\n            while i < len(events) and j == events[i][0]:\n                count += events[i][1]\n                i += 1\n            request_count[j] = count\n            \n        request_count.sort()\n        nums.sort()\n        result = 0\n        while request_count and request_count[-1] > 0:\n            result += request_count.pop() * nums.pop()\n        return result % 1_000_000_007", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        freq = [0] * (n + 1)\n        for i, j in requests:\n            freq[i] += 1\n            freq[j + 1] -= 1\n        for i in range(1, n + 1):\n            freq[i] += freq[i - 1]\n        freq.sort(reverse=True)\n        nums.sort(reverse=True)\n        res = 0\n        for i in range(n):\n            res += nums[i] * freq[i]\n        return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        starts = []\n        ends = []\n        for x, y in requests:\n            starts.append(x)\n            ends.append(y)\n        \n        starts.sort()\n        ends.sort()\n        \n        freqs = [bisect.bisect_right(starts, i) - bisect.bisect_left(ends, i) for i in range(len(nums))]\n        freqs.sort()\n        nums.sort()\n        res = 0\n        for i, j in zip(freqs, nums):\n            res += (i * j)\n        return res % (10**9 + 7)\n", "from bisect import bisect_left, bisect_right\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        s = sorted([a for a, _ in requests])\n        e = sorted([a for _, a in requests])\n\\t\\t\n        freq = [bisect_right(s, i) - bisect_left(e, i) for i in range(len(nums))]\n\\t\\t\\t\n        res = sum(f * n for f, n in zip(sorted(freq), sorted(nums)))\n        return res % int(1e9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        n = len(nums)\n        \n        cnt = [0] * n\n        for st, ed in requests:\n            cnt[ed] += 1\n            if st > 0: cnt[st-1] -= 1\n        for i in range(n-2, -1, -1):\n            cnt[i] += cnt[i+1]\n                \n        cnt.sort(reverse=1)\n        nums.sort(reverse=1)\n        ans = 0\n        for c, x in zip(cnt, nums):\n            if c == 0: break\n            ans += c * x\n        return ans % MOD", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        cnt = [0] * len(nums)\n        requests = sorted(requests, key = lambda x: -x[0])\n        q = []\n        for idx in range(len(nums)):\n            while requests and idx >= requests[-1][0]:\n                s, e = requests.pop()\n                heapq.heappush(q, (e, s))\n            while q and idx > q[0][0]:\n                heapq.heappop(q)\n                \n            cnt[idx] = len(q)\n        \n        cnt.sort()\n        nums.sort()\n        return sum(cnt[idx] * nums[idx] for idx in range(len(nums))) % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        heap = []#heap\n        dict = defaultdict(int)\n        requests.sort()\n        count = 0\n        start = 0\n        for i in requests:\n            while heap and heap[0] < i[0]:#\u82e5\u5728\u65b0\u7684request\u9032\u4f86\u524d\uff0c\u6709\u820a\u7684request\u7d50\u5c3e\u66f4\u65e9\u7d50\u675f\n                heap_pop = heapq.heappop(heap)#\u5fc5\u9808pop\u6389\n                dict[count] += heap_pop + 1 - start#\u9019\u500b\u820a\u7684request\u7d50\u5c3e+1\u6e1b\u53bb\u524d\u4e00\u500bstart\uff0c\u9019\u662f\u4e00\u6bb5interval\uff0c\u9019\u6bb5interval\u7684\u91cd\u758a\u9ad8\u5ea6\u70bacount\n                start = heap_pop + 1#\u540c\u6642\u66f4\u65b0\u9019\u500b\u9019\u500brequest\u7684\u7d50\u5c3e+1\u70ba\u65b0\u7684start\n                count -= 1#\u56e0\u70ba\u820a\u7684request pop\u6240\u4ee5count-1\n            heapq.heappush(heap, i[1])#\u7528heap\u5b58\u9019\u500brequest\u7684\u7d50\u5c3e\n            dict[count] += i[0] - start#\u7576\u524d\u9019\u500brequest\u7684\u8d77\u59cb\u6e1b\u6389\u524d\u4e00\u500bstart\uff0c\u9019\u662f\u4e00\u6bb5interval\uff0c\u9019\u6bb5interval\u7684\u91cd\u758a\u9ad8\u5ea6\u70bacount\n            start = i[0]#\u540c\u6642\u66f4\u65b0\u9019\u500b\u9019\u500brequest\u7684\u8d77\u59cb\u70ba\u65b0\u7684start\n            count += 1#\u56e0\u70ba\u662f\u65b0\u7684request\u9032\u4f86\uff0c\u6240\u4ee5count+1\n        while heap:#\u628a\u6700\u5f8c\u9084\u5728heap\u5167\u7684request pop\u6389\n            heap_pop = heapq.heappop(heap)\n            dict[count] += heap_pop + 1 - start\n            start = heap_pop + 1\n            count -= 1\n        nums.sort(reverse = True)\n        index = 0\n        res = 0\n        sort_key = sorted(list(dict.keys()), reverse = True)#\u6700\u5f8c\u6309\u7167count\u7684\u6578\u91cf\u591a\u5be1\u6392\u5e8f\uff0ccount\u8d8a\u591a\uff0c\u5c31\u8b93\u4ed6\u4e58\u4e0a\u8d8a\u5927\u7684\u503c\n        for key in sort_key:\n            res += key*sum(nums[index:index+dict[key]])#\u628a\u7d50\u679c\u4e58\u8d77\u4f86\n            res %= (10**9+7)\n            index += dict[key]\n        return res\n        \n        \n        # nums.sort(reverse = True)#request\u7528\u4f86\u8a18\u9304\u6bcf\u500b\u6642\u9593\u9ede\u7684\u8d77\u59cb\u8ddf\u7d50\u675f\u6578\u91cf\uff0c\u5982\u904e\u8d77\u59cb\u78b0\u5230\u7d50\u675f\u525b\u597d\u62b5\u6d88\uff0c\u7136\u5f8c\u518d\u7528\u7b2c\u4e8c\u500bfor\u4fee\u6539\u6bcf\u500b\u6642\u9593\u9ederoom\u7684\u6578\u91cf(\u7b49\u65bc\u7576\u524dcount\u7684\u6578\u91cf)\uff0c\u6700\u5f8csort\uff0c\u518d\u76f8\u4e58\n        # print(nums)\n        # request = len(nums)*[0]\n        # for i in range(len(requests)):\n        #     request[requests[i][0]] += 1\n        #     if requests[i][1]+1 < len(nums):\n        #         request[requests[i][1]+1] -= 1\n        # print(request)\n        # count = 0\n        # for i in range(len(request)):\n        #     count += request[i]\n        #     request[i] = count\n        # request.sort(reverse = True)\n        # res = 0\n        # for i in range(len(request)):\n        #     res = (res + request[i]*nums[i]) % (10**9+7)\n        # return res\n        \n                \n        \n        # t = len(nums)*[0]#TLE\n        # for a,b in requests:\n        #     for j in range(a, b+1):\n        #         t[j] += 1\n        # nums.sort()\n        # t.sort()\n        # res = 0\n        # for i in range(len(nums)-1, -1, -1):\n        #     if t[i] == 0:\n        #         break\n        #     res += nums[i]*t[i]\n        #     res %= (10**9+7)\n        # return res\n", "class Solution:\n    def maxSumRangeQuery(self, A, req):\n        n = len(A)\n        count = [0] * (n + 1)\n\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n\n        count = list(accumulate(count))[:-1]\n        count.sort()\n        A.sort()\n        return sum([count[i]*A[i] for i in range(n)]) % (10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        count = [0]*(len(nums)+1)\n        \n        for i,j in requests:\n            count[i] += 1\n            count[j+1] -= 1\n        \n        for i in range(1,len(count)):\n            count[i] += count[i-1]\n        \n        \n        total = 0\n        for a,b in zip(sorted(count[:-1]),sorted(nums)):\n            total += a*b\n        \n        return total%(10**9+7)", "from collections import defaultdict\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        arr = [0]*len(nums)\n        for i,j in requests:\n            arr[i]+=1\n            if j+1<len(arr):\n                arr[j+1]-=1\n        for i in range(1, len(arr)):\n            arr[i]+=arr[i-1]\n            \n        arr.sort()\n        nums.sort()\n        res = 0\n        \n        for i,j in zip(arr, nums):\n            res+=(i*j)\n            \n        return res%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        # s,e, \n        # at most nlogn\n        cnt = [0,0]\n        mod = 10**9+7\n        requests.sort()\n        n = len(nums)\n        cnt = [0]*(n)\n        for s,e in requests:\n            cnt[s]+=1\n            if e+1<n:\n                cnt[e+1]-=1\n            \n        print(cnt)\n        real_cnt = []\n        for c in cnt:\n            real_cnt += [c+(real_cnt[-1] if real_cnt else 0)]\n        \n        cnt = real_cnt\n        cnt.sort()\n        nums.sort()\n        print(cnt,nums)\n\n        res = 0\n        for n,c in zip(nums,cnt):\n            res+=n*c\n        return res%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        nums.sort(reverse=True)\n        reqs = defaultdict(int)\n        for start, end in requests:\n            reqs[start] += 1\n            reqs[end + 1] -= 1\n        counts = defaultdict(int)\n        h = 0\n        last = -1\n        for i in sorted(reqs.keys()):\n            if h > 0:\n                counts[h] += max(0, i - last)\n            h += reqs[i]\n            last = i\n        res = 0\n        i = 0\n        n = len(nums)\n        for h, c in sorted(list(counts.items()), reverse=True):\n            for j in range(c):\n                if i == n:\n                    break\n                num = nums[i]\n                res += num * h\n                i += 1\n            res %= MOD\n            if i == n:\n                break\n        return res\n", "class Solution:\n    def maxSumRangeQuery(self, a: List[int], req: List[List[int]]) -> int:\n        n = len(a)\n        count = [0] * (n + 1)\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for count, value in zip(sorted(count[:-1]), sorted(a)):\n            res += count * value\n        return res % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:    \n        MOD = (10 ** 9 + 7)\n                \n        request_counts = [0 for i in range(len(nums))]\n        for l, r in requests:\n            request_counts[l] += 1\n            if r + 1 < len(nums):\n                request_counts[r + 1] -= 1\n        for i in range(1, len(nums)):\n            request_counts[i] += request_counts[i - 1]\n        request_counts.sort()\n        nums.sort()\n        \n        result = 0\n        for r, n in zip(request_counts, nums):\n            result = (result + r * n) % MOD\n            \n        return result\n        \n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        start = collections.defaultdict(int)\n        end = collections.defaultdict(int)\n        min_start = 10000\n        max_end = 0\n        for request in requests:\n            start[request[0]] += 1\n            end[request[1]] += 1\n            min_start = min(min_start, request[0])\n            max_end = max(max_end, request[1])\n        \n        cnt = 0\n        cnt_dic = {}\n        for num in range(min_start, max_end+1):\n            if num in start:\n                cnt += start[num]\n            if cnt > 0:\n                cnt_dic[num] = cnt\n            if num in end:\n                cnt -= end[num]\n        \n        cnt_sorted = sorted(cnt_dic.values(), key = lambda x : -x)\n        num_sorted = sorted(nums, key = lambda x : -x)\n        result = 0\n        for i, cnt in enumerate(cnt_sorted):\n            result += num_sorted[i] * cnt\n        return result % 1000000007", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        len_nums = len(nums)\n        frequencies = [0] * (len_nums + 1)\n        for start, end in requests:\n            frequencies[start] += 1\n            frequencies[end + 1] -= 1\n        for k in range(1, len_nums):\n            frequencies[k] += frequencies[k - 1]\n        frequencies.sort(reverse=True)\n        nums.sort(reverse=True)\n        max_sum = 0\n        zipper = list(zip(nums, frequencies))\n        for num, frequency in zipper:\n            max_sum += num * frequency\n        return max_sum % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        count = [0] * (len(nums) + 1)\n        mod = 10 ** 9 + 7\n                \n        for r in requests:\n            count[r[0]] += 1\n            count[r[1]+1] -= 1\n        for i in range(1, len(count)):\n            count[i] += count[i-1]\n                 \n        res = 0\n        count.sort(reverse = True)\n        nums.sort(reverse = True)\n        for i in range(len(count)-1): \n            res = (res + (nums[i] * count[i])) % mod\n            if count[i] == 0:\n                break\n                \n        return res\n", "import heapq\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        mymap = collections.defaultdict(int)\n        n = len(nums)\n        freqs = [0]*(n+1)\n        for i, j in requests:\n            freqs[i] += 1         \n            freqs[j+1] -= 1\n            \n#         MADE ... prefix Sum ... algo ... to make if proper normalize ... the number of requests\n#         thru indexes..\n        for i in range(1, n+1):\n            freqs[i] += freqs[i-1]\n        \n        # THIS IS TAKING o(n^2):- .... need to reduce this ... later part is amazingly fast\n#         TLE -------------------------------------------------------------------------------------------      so .. we implemented above logic ... to reduce complexity\n\n        \n        # for req in requests:\n        #     for ind in range(req[0], req[1]+1):\n        #         mymap[ind] += 1\n        \n        \n        \n#         freqs = sorted(mymap.values(), reverse=True)\n        freqs = sorted(freqs[:-1], reverse=True)\n    \n    \n#          CAN... DO HEAP ... also ... can do ... sorting of Array\n        heap = [(-n, n) for n in nums]\n        \n        heapq.heapify(heap)\n        \n        tot = 0\n        for i, freq in enumerate(freqs):\n            num = heapq.heappop(heap)[1]\n            tot += num*freq\n            tot %= (10**9 + 7)\n            \n        return tot % (10**9 + 7)", "class Solution:\n    # https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854206/JavaC%2B%2BPython-Sweep-Line\n    # https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854149/C%2B%2BJava-O(n-log-n)\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort(reverse = True)\n        n = len(nums)\n        counter = [0 for _ in range(n + 1)]\n        for i, j in requests:\n            counter[i] += 1\n            counter[j + 1] -= 1\n        for i in range(1, n + 1):\n            counter[i] += counter[i - 1]\n        counter.sort(reverse = True)\n        res = 0\n        for i in range(n):\n            res += counter[i] * nums[i]\n        return res % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, a: List[int], b: List[List[int]]) -> int:\n        n = len(a)\n        p = [0] * (n + 1)\n        for x in b:\n            p[x[0]] += 1\n            p[x[1] + 1] -= 1\n        pref = [0] * n\n        pref[0] = p[0]\n        for i in range(1, n):\n            pref[i] = p[i] + pref[i - 1]\n        # pref.pop()\n        # print(pref)\n        pref.sort(reverse=True)\n        a.sort(reverse=True)\n        s = 0\n        for i in range(n):\n            s += pref[i] * a[i]\n        return s % (10**9 + 7)\n", "mod = 10**9+7\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        arr = [0]*(n+1) # add extra element for handel n+1 case\n        for i, j in requests:\n            arr[i]  += 1\n            arr[j+1] -= 1\n        for i in range(1, n+1):\n            arr[i] += arr[i-1]\n        arr = arr[:n] # remove extra element\n        nums.sort()\n        arr.sort()\n        ans = 0\n        for i in range(n):\n            ans += nums[i] * arr[i]\n        return ans%mod", "from collections import defaultdict\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        count_map = defaultdict(lambda: 0)\n        \n        sorted_requests_start = sorted(requests, key=lambda x: x[0])\n        sorted_requests_end = sorted(requests, key=lambda x: x[1])\n        max_i = len(nums)\n        start_ptr = 0\n        ended_ptr = 0\n        \n        ongoing_request_list = []\n        curr_request_count = 0\n        for i in range(max_i):\n            while start_ptr < len(requests) and sorted_requests_start[start_ptr][0] == i:\n                curr_request_count += 1\n                start_ptr += 1\n            while ended_ptr < len(requests) and sorted_requests_end[ended_ptr][1] < i:\n                curr_request_count -= 1   \n                ended_ptr += 1\n            ongoing_request_list.append(curr_request_count)\n        \n        sorted_pairs = sorted(ongoing_request_list, key=lambda x: -x)\n        sorted_nums = sorted(nums, key=lambda x: -x)\n        \n        return int(sum(map(lambda x, y: x*y, sorted_pairs, sorted_nums)) % (1e9+7))\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mod = 10**9 + 7\n        m = len(nums)\n        rank = [0] * (m + 1)\n        for i, j in requests:\n            rank[i] += 1\n            rank[j + 1] -= 1\n        \n        for i in range(1, m):\n            rank[i] += rank[i - 1]\n        \n        ans = 0\n        rank = rank[:m]\n        nums.sort()\n        rank.sort()\n        for i, count in enumerate(rank):\n            ans += nums[i] * count\n        \n        return ans % mod\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        n = len(nums)\n        counter = [0] * n\n        for start, end in requests:\n            if start < n:\n                counter[start] += 1\n            if end < n - 1:\n                counter[end + 1] -= 1\n        occurences = sorted(list(accumulate(counter)))\n        nums.sort()\n        res = sum([n * o for n, o in zip(nums, occurences)])\n        return res % MOD", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        n=len(nums)\n        prefix=[0 for i in range(len(nums))]\n        for start,end in requests:\n            prefix[start]+=1\n            if end!=n-1:\n                prefix[end+1]-=1\n        for i in range(1,len(nums)):\n            prefix[i]+=prefix[i-1]\n        prefix.sort()\n        nums.sort()\n        res=0\n        mod=10**9+7\n        for val,time in zip(prefix,nums):\n            res+=val*time\n        return res%mod\n            \n                \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        # permutation\n        # requests where requests[i] = [starti, endi]\n        # ith request asks for sum of \n        from operator import add\n        lenn = len(nums)\n        ranks = [0] * (lenn + 1)\n        for i, j in requests:\n            ranks[i]  += 1\n            ranks[j+1] -= 1\n        for i in range(1, lenn + 1):\n            ranks[i] += ranks[i-1]\n        ranks = ranks[:lenn]\n        return sum(x*y for x, y in zip(sorted(ranks), sorted(nums))) % (10**9 + 7)\n    \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        dp = [0]*len(nums)\n        \n        for i in range(len(requests)):\n            dp[requests[i][0]] += 1\n            if requests[i][1]<len(nums)-1:\n                dp[requests[i][1]+1] -= 1\n        \n        for i in range(1, len(dp)):\n            dp[i] += dp[i-1]\n        \n        dp.sort(reverse=True)\n        nums.sort(reverse=True)\n        ans = 0\n        mod = int(1e9)+7\n        for i in range(len(nums)):\n            ans += nums[i]*dp[i]\n            ans = ans%mod\n        \n        return ans\n        \n", "import heapq\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        \n        \n        mymap = collections.defaultdict(int)\n        n = len(nums)\n        freqs = [0]*(n+1)\n        for i, j in requests:\n            freqs[i] += 1         \n            freqs[j+1] -= 1\n            \n#         MADE ... prefix Sum ... algo ... to make if proper normalize ... the number of requests\n#         thru indexes..\n        for i in range(1, n+1):\n            freqs[i] += freqs[i-1]\n            \n        \n            \n            \n        \n        # THIS IS TAKING o(n^2):- .... need to reduce this ... later part is amazingly fast\n#         TLE -------------------------------------------------------------------------------------------      so .. we implemented above logic ... to reduce complexity\n\n        \n        # for req in requests:\n        #     for ind in range(req[0], req[1]+1):\n        #         mymap[ind] += 1\n        \n        \n        \n#         freqs = sorted(mymap.values(), reverse=True)\n        freqs = sorted(freqs[:-1], reverse=True)\n        heap = [(-n, n) for n in nums]\n        \n        heapq.heapify(heap)\n        \n        tot = 0\n        for i, freq in enumerate(freqs):\n            num = heapq.heappop(heap)[1]\n            tot += num*freq\n            tot %= (10**9 + 7)\n            \n        return tot % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        called_times = [0] * n\n        a = [0] * n\n        mod = 10**9 + 7\n        \n        for i,j in requests:\n            a[j] += 1\n            if i-1 >= 0:\n                a[i-1] -= 1\n        c = 0\n        for i in range(n-1,-1,-1):\n            c += a[i]\n            called_times[i] = c\n            \n        called_times.sort(reverse = True)\n        nums.sort(reverse = True)\n        ans = 0\n        for i in range(n):\n            ans += called_times[i]*nums[i]\n            ans %= mod\n            if called_times[i] == 0:\n                break\n        return ans\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mod = 10**9+7\n        n = len(nums)\n        \n        freq = [0]*n\n        heap = []\n        requests.sort()\n        j = 0\n        for i in range(n):\n            while j<len(requests) and requests[j][0] <= i:\n                heapq.heappush(heap, (requests[j][1], requests[j][0]))\n                j += 1\n            while heap and heap[0][0] < i:\n                heapq.heappop(heap)\n            freq[i] = len(heap)\n        \n        freq.sort(reverse = True)\n        nums.sort(reverse = True)\n        return sum([freq[i]*nums[i] for i in range(n)]) % mod", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        ps_start=collections.defaultdict(int)\n        ps_end=collections.defaultdict(int)\n        for s,e in requests:\n            ps_start[s]-=1\n            ps_end[e]+=1\n        res=[]\n        for p in ps_start:res.append([p,ps_start[p]])\n        for p in ps_end:res.append([p,ps_end[p]])\n        res.sort()\n        \n        \n        freq=[0 for i in range(len(nums))]\n        # print(res)\n        prev,count=0,0\n        for p,v in res:\n            if v<0:#start\n                for i in range(prev,p):\n                    freq[i]+=count\n                prev=p\n                count-=v\n            else:\n                for i in range(prev,p+1):\n                    freq[i]+=count\n                prev=p+1\n                count-=v\n        freq.sort()\n        ans=0\n        k=0\n        # print(freq)\n        nums.sort()\n        mod=1000000007\n        for f in freq:\n            ans+= (f*nums[k])%mod\n            k+=1\n        return ans%mod\n            \n", "class Solution:\n    def maxSumRangeQuery(self, n: List[int], r: List[List[int]]) -> int:\n        r.sort()\n        n.sort(reverse=True)\n        s = sorted([x for x, y in r])\n        t = sorted([y for x, y in r])\n        c = collections.Counter()\n        x = 0\n        si, ti = 0, 0\n        for i in range(s[0], t[-1] + 1):\n            while si < len(s) and s[si] == i:\n                x += 1\n                si += 1\n            c[x] += 1\n            while ti < len(t) and t[ti] == i:\n                x -= 1\n                ti += 1\n        res = 0\n        print(s, t)\n        print(c.most_common())\n        ni = 0\n        for k in sorted(c.elements(), reverse=True):\n            res += k * n[ni]\n            ni += 1\n            \n        return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:\n        n = len(A)\n        count = [0] * (n + 1)\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(A)):\n            res += v * c\n        return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        values = [0] * (n+1)\n        for i in requests:\n            values[i[0]] += 1\n            values[i[1]+1] -= 1\n        for i in range(1, n):\n            values[i] += values[i-1]\n        values.sort(reverse = True)\n        nums.sort(reverse = True)\n        # print(values)\n        ans = 0;\n        mod = int(1e9) + 7;\n        for i in range(n):\n            ans += (values[i] * nums[i])\n            ans %= mod;\n        return ans\n        \n        \n        \n#         requests.sort(key = lambda x: x[0] - x[1])\n#         # print(requests)\n#         sz = requests[0][1] - requests[0][0] + 1\n#         nums.sort(reverse = True)\n#         ans = 0\n#         for i in range(sz):\n#             ans += nums[i]\n#             ans %= mod\n#         return ans;\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        cnt = [0] * (len(nums) + 2)\n        for a, b in requests:\n            cnt[a] += 1\n            cnt[b + 1] -= 1\n        for i in range(len(nums)):\n            cnt[i] += cnt[i - 1]\n        cnt.sort(reverse=True)\n        nums.sort(reverse=True)\n        return sum(a * b for a, b in zip(cnt, nums)) % (10 ** 9 + 7)", "from collections import Counter\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9+7\n        c = 0\n        \n        sn = list(sorted(nums))\n        starts, ends = Counter(), Counter()\n        \n        for s, e in requests:\n            starts[s] += 1\n            ends[e+1] += 1\n            \n        # print(starts)\n        # print(ends)\n        \n        repeats = []\n        ranges = 0\n        for i, _ in enumerate(nums):\n            ranges += starts[i] - ends[i]\n            repeats.append(ranges)\n        \n        sr = list(sorted(repeats))\n        # print(sn)\n        # print(sr)\n        for i, r in enumerate(repeats):\n            c += sn[i] * sr[i]       \n        \n        return c % MOD\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        d = [0] * len(nums)\n        r = [0] * len(nums)\n        c = 0\n        j = 0\n        requests.sort()\n        for i in range(len(nums)):\n            d[i] += c\n            c -= r[i]\n            r[i] = 0\n            while j < len(requests) and requests[j][0] == i:\n                d[i] += 1\n                if requests[j][1] > i:\n                    c += 1\n                    r[requests[j][1]] += 1\n                j += 1\n                    \n        ans = 0\n        for a, b in zip(sorted(nums, reverse=True), sorted(d, reverse=True)):\n            if not b:\n                break\n            ans += a * b % 1000000007\n        return ans % 1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9+7\n        \n        nums.sort()\n        ends = sorted(requests,key=lambda x: x[1])\n        starts = sorted(requests, key=lambda x: x[0])\n        \n        ends = [x[1] for x in ends]\n        starts = [x[0] for x in starts]\n        \n        n = len(nums)\n        counts = []\n        \n        #print(starts)\n        #print(ends)\n        for i in range(n):\n            endsOnBehind = len(ends)-bisect.bisect_left(ends, i)\n            startsToRight = len(starts)-bisect.bisect_right(starts, i)\n            \n            \n            counts.append(endsOnBehind-startsToRight)\n        \n        #print(counts)\n        counts.sort()\n        \n        j = n-1\n        ans = 0\n        \n        \n        for i in range(len(counts)-1, -1, -1):\n            if counts[i]==0:\n                break\n            \n            ans += counts[i]*nums[j]\n            ans %= MOD\n            j-=1\n        \n        return ans\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0 for _ in range(n)]\n        h = []\n        requests.sort(key = lambda x: x[0])\n        start = 0\n        for s,e in requests:\n            while h and h[0] < s:\n                for i in range(start, h[0]+1):\n                    count[i] += len(h)\n                start = h[0]+1\n                heapq.heappop(h)\n            for i in range(start, s):\n                count[i] += len(h)\n            start = s\n            heapq.heappush(h,e)\n        while h:\n            for i in range(start,h[0]+1):\n                count[i] += len(h)\n            start = h[0]+1\n            heapq.heappop(h)\n        mod = 10**9+7\n        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod\n                \n                    \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        result = 0\n        nums.sort()\n        n = len(nums)\n        LARGE = int(1e9 + 7)\n        events = []\n        for re in requests:\n            events.append([re[0], 1])\n            events.append([re[1] + 1, -1])\n        # count.sort()\n        events.sort()\n        # print(events)\n        \n        prev = -1\n        result = 0\n        index = 0\n        count = [-1 for i in range(n + 1)]\n        now = 0\n        for num, change in events:\n            now += change\n            count[num] = now\n        for i in range(n):\n            if (count[i] == -1):\n                if i == 0:\n                    count[i] = 0\n                else:\n                    count[i] = count[i - 1]\n        count.pop()\n        count.sort()\n        \n        # print(count)\n        return sum([count[i] * nums[i] for i in range(n)]) % LARGE", "class Solution:\n    def maxSumRangeQuery(self, ar: List[int], requests: List[List[int]]) -> int:\n        n=len(ar)\n        pref=[0 for i in range (n)]\n        for i in requests:\n            pref[i[0]]+=1\n            if i[1]+1<n:\n                pref[i[1]+1]-=1\n        #print(pref)\n        for i in range (1,n):\n            pref[i]=pref[i-1]+pref[i]\n        #print(pref)\n        ar.sort(reverse=True)\n        pref.sort(reverse=True)\n        res=0\n        mod=(10**9)+7\n        for i,j in zip(ar,pref):\n            res=(res+(i*j))%mod\n        return res\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        pts = []\n        for start, end in requests:\n            pts.append((start, 1))\n            pts.append((end + 1, -1)) # open bracket\n        \n        pts.sort(key = lambda x: (x[0], x[1]))\n        \n        N = len(nums)\n        cnts = []\n        # 2 pointers\n        j = 0\n        cur = 0\n        for i in range(N):\n            if j == len(pts):\n                cnts.append(cur)\n                continue\n            if pts[j][0] > i:\n                cnts.append(cur)\n            elif pts[j][0] == i:\n                while j < len(pts) and pts[j][0] == i:\n                    cur += pts[j][1]\n                    j += 1\n                cnts.append(cur)\n        cnts.sort()\n        nums.sort()\n        ans = 0\n        MOD = 10 ** 9 + 7\n        for c, n in zip(cnts, nums):\n            ans += c * n\n            ans %= MOD\n        return ans\n            \n\n            \n        \n        \n        \n        \n        \n        \n        \n        N = len(nums)\n        tree = [0] * (4 * N)\n        lazy = [0] * (4 * N)\n        arr = nums\n        def _push_down(rt, diff):\n            lazy[rt * 2 + 1] += diff\n            lazy[rt * 2 + 2] += diff\n        def update_range_by_one(rt, lo, hi, i, j):\n            if j < lo or i > hi: return\n            if lazy[rt] != 0:\n                tree[rt] += (hi - lo + 1) * lazy[rt]\n                if lo != hi:\n                    _push_down(rt, lazy[rt])\n                lazy[rt] = 0\n            if lo >= i and hi <= j:\n                tree[rt] += (hi - lo + 1)\n                if lo != hi:\n                    _push_down(rt, 1)\n                return\n            mid = (lo + hi) // 2\n            update_range_by_one(rt * 2 + 1, lo, mid, i, j)\n            update_range_by_one(rt * 2 + 2, mid + 1, hi, i, j)\n            tree[rt] = tree[2 * rt + 1] + tree[2 * rt + 2]\n        \n        def query(rt, lo, hi, i):\n            if lazy[rt] != 0:\n                tree[rt] += (hi - lo + 1) * lazy[rt]\n                if lo != hi:\n                    _push_down(rt, lazy[rt])\n                lazy[rt] = 0\n            if lo == hi == i: return tree[rt]\n            mid = (lo + hi) // 2\n            if i <= mid: return query(rt * 2 + 1, lo, mid, i)\n            else: return query(rt * 2 + 2, mid + 1, hi, i)\n                \n        \n        MOD = 10 ** 9 + 7\n        for i, j in requests:\n            update_range_by_one(0, 0, N - 1, i, j)\n        \n        cnts = []\n        for i in range(N):\n            cnts.append(query(0, 0, N - 1, i))\n        cnts.sort()\n        nums.sort()\n        \n        ans = 0\n        for c, n in zip(cnts, nums):\n            ans += c * n\n            ans %= MOD\n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        ps_start=collections.defaultdict(int)\n        ps_end=collections.defaultdict(int)\n        for s,e in requests:\n            ps_start[s]-=1\n            ps_end[e]+=1\n        res=[]\n        for p in ps_start:res.append([p,ps_start[p]])\n        for p in ps_end:res.append([p,ps_end[p]])\n        res.sort()\n        \n        \n        freq=[[i,0] for i in range(len(nums))]\n        # print(res)\n        prev,count=0,0\n        for p,v in res:\n            if v<0:#start\n                for i in range(prev,p):\n                    freq[i][1]+=count\n                prev=p\n                count-=v\n            else:\n                for i in range(prev,p+1):\n                    freq[i][1]+=count\n                prev=p+1\n                count-=v\n        freq.sort(key=lambda x:x[1])\n        ans=0\n        k=0\n        # print(freq)\n        nums.sort()\n        mod=1000000007\n        for i,f in freq:\n            ans+= (f*nums[k])%mod\n            k+=1\n        return ans%mod\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort(reverse=True)\n        a = [0]*(len(nums)+1)\n        for start, end in requests:\n            a[start] += 1\n            a[end+1] -= 1\n        for ind, val in enumerate(a[1:], 1):\n            a[ind] += a[ind-1]\n        a.sort(reverse=True)\n        total = 0\n        for k, val in zip(a, nums):\n            total += k*val\n        return total%(10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0 for _ in range(n)]\n        h = []\n        requests.sort(key = lambda x: x[0])\n        start = 0\n        for s,e in requests:\n            while h and h[0] < s:\n                for i in range(start, h[0]+1):\n                    count[i] += len(h)\n                start = h[0]+1\n                heapq.heappop(h)\n            for i in range(start, s):\n                count[i] += len(h)\n            start = s\n            heapq.heappush(h,e)\n        while h:\n            for i in range(start,h[0]+1):\n                count[i] += len(h)\n            start = h[0]+1\n            heapq.heappop(h)  \n        mod = 10**9+7\n        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod\n                \n                    \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = (10**9 + 7)\n        n = len(nums)\n        count = [0]*(n+1)\n        for i, j in requests:\n            count[i] += 1\n            count[j+1] -= 1\n        for i in range(1, n+1):\n            count[i] += count[i-1]\n        ret = 0\n        for a, b in zip(sorted(count[:-1]), sorted(nums)):\n            ret += a*b\n        return ret % MOD\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n\n        N = len(nums)\n        C = [0] * (N + 1)\n        \n        for s, e in requests:\n            C[s] += 1\n            C[e + 1] -= 1\n            \n        for i in range(1, N):\n            C[i] += C[i - 1]\n        \n        C.pop()\n            \n        \n        perm = [0] * N        \n        csort = [i for i, _ in sorted([(i, c) for i, c in enumerate(C)], key=lambda x: x[1])]\n        \n        for i, n in zip(csort, sorted(nums)):\n            perm[i] = n\n            \n        for i in range(1, N):\n            perm[i] += perm[i - 1]\n            \n        result = 0\n        for s, e in requests:\n            if s == 0:\n                result += perm[e]\n            else:\n                result += perm[e] - perm[s - 1]\n                \n        return result % (10 ** 9 + 7)\n            \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        d = [0] * len(nums)\n        r = defaultdict(int)\n        c = 0\n        j = 0\n        requests.sort()\n        for i in range(len(nums)):\n            d[i] += c\n            c -= r[i]\n            r[i] = 0\n            while j < len(requests) and requests[j][0] == i:\n                d[i] += 1\n                if requests[j][1] > i:\n                    c += 1\n                    r[requests[j][1]] += 1\n                j += 1\n                    \n        ans = 0\n        for a, b in zip(sorted(nums, reverse=True), sorted(d, reverse=True)):\n            if not b:\n                break\n            ans += a * b % 1000000007\n        return ans % 1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mod = 10**9 + 7\n        n = len(nums)\n        counts = [0] * n\n        \n        for start, end in requests:\n            counts[start] += 1\n            if end < n - 1:\n                counts[end + 1] -= 1\n        \n        cur_count = 0\n        for i in range(n):\n            cur_count += counts[i]\n            counts[i] = cur_count\n        \n        nums.sort()\n        counts.sort()\n        res = 0\n        for count, num in zip(counts, nums):\n            res = (res + count * num) % mod\n        \n        return res\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        arr = [0]*(len(nums)+1)\n        for i, j in requests:\n            arr[i]  += 1\n            arr[j+1] -= 1\n        for i in range(1, len(nums)+1):\n            arr[i] += arr[i-1]\n        arr=arr[:len(nums)]\n        arr.sort()\n        nums.sort()\n        s=0\n        for i in range(len(arr)):\n            s+=nums[i]*arr[i]\n        return s%(10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0 for _ in range(n)]\n        h = []\n        requests.sort(key = lambda x: x[0])\n        start = 0\n        for s,e in requests:\n            while h and h[0] < s:\n                for i in range(start, h[0]+1):\n                    count[i] += len(h)\n                start = h[0]+1\n                heapq.heappop(h)\n            for i in range(start, s):\n                count[i] += len(h)\n            start = s\n            heapq.heappush(h,e)\n        while h:\n            for i in range(start,h[0]+1):\n                count[i] += len(h)\n            start = h[0]+1\n            heapq.heappop(h)  \n        print(count)\n        mod = 10**9+7\n        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod\n                \n                    \n", "class Solution:\n    def maxSumRangeQuery(self, nums, requests) -> int:\n        mod_num = 10 ** 9 + 7\n        n = len(nums)\n        freq_arr = [0 for _ in range(n + 1)]\n        for i, j in requests:\n            freq_arr[i] += 1\n            freq_arr[j+1] -= 1\n        for i in range(1, n + 1):\n            freq_arr[i] += freq_arr[i-1]\n        result = sum([num * freq % mod_num for num, freq in zip(sorted(nums), sorted(freq_arr[:n]))]) % mod_num\n        return result", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        d = [0] * len(nums)\n        r = defaultdict(int)\n        c = 0\n        requests.sort()\n        j = 0\n        for i in range(len(nums)):\n            if j >= len(requests):\n                d[i] += c\n                c -= r[i]\n                r[i] = 0\n            elif requests[j][0] > i:\n                d[i] = c\n                c -= r[i]\n                r[i] = 0\n            else:\n                d[i] += c\n                c -= r[i]\n                r[i] = 0\n                while j < len(requests) and requests[j][0] == i:\n                    d[i] += 1\n                    if requests[j][1] > i:\n                        c += 1\n                        r[requests[j][1]] += 1\n                    j += 1\n        #     print(i, c, r)\n        # print(requests)\n        # print(d)\n        ans = 0\n        for a, b in zip(sorted(nums, reverse=True), sorted(d, reverse=True)):\n            ans += a * b % 1000000007\n        return ans % 1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        '''\n        Count the frequency of each index and re-arrange\n        '''\n        freq = [0] * (len(nums) + 1)\n        for l in requests:\n            freq[l[0]] += 1\n            freq[l[1]+1] -= 1\n        for i in range(1, len(freq)):\n            freq[i] += freq[i-1]\n        ans = 0\n        for x, y in zip(sorted(freq[:-1]), sorted(nums)):\n            ans += x * y\n        return ans % 1000000007\n", "from collections import Counter\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        count = [0] * (len(nums)+1)\n        for start, end in requests:\n            count[start] += 1\n            count[end+1] -= 1\n        for i in range(1, len(nums)+1):\n            count[i] += count[i-1]\n        count = count[:-1]\n        summ = 0\n        for num, c in zip(sorted(nums), sorted(count)):\n            summ += num *c\n        return summ % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9+7\n        \n        nums.sort()\n        ends = sorted(requests,key=lambda x: x[1])\n        starts = sorted(requests, key=lambda x: x[0])\n        \n        ends = [x[1] for x in ends]\n        starts = [x[0] for x in starts]\n        \n        countends = collections.Counter([r[1] for r in requests])\n        countstarts = collections.Counter([r[0] for r in requests])\n        \n        n = len(nums)\n        counts = []\n        \n        #print(starts)\n        #print(ends)\n        for i in range(n):\n            endsOnBehind = len(ends)-bisect.bisect_left(ends, i)\n            startsToRight = len(starts)-bisect.bisect_right(starts, i)\n            \n            \n            counts.append(endsOnBehind-startsToRight)\n        \n        #print(counts)\n        counts.sort()\n        \n        j = n-1\n        ans = 0\n        \n        \n        for i in range(len(counts)-1, -1, -1):\n            if counts[i]==0:\n                break\n            \n            ans += counts[i]*nums[j]\n            ans %= MOD\n            j-=1\n        \n        return ans\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], req: List[List[int]]) -> int:\n        n = len(nums)\n       \n        count = [0] * (n + 1)\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(nums)):\n            res += v * c\n        return res % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        requests = sorted(requests)\n        repeated, dp, idx = [],[],0\n        for i in range(len(nums)):\n            while dp and dp[0] < i:\n                heapq.heappop(dp)\n            while idx < len(requests) and requests[idx][0] <= i:\n                heapq.heappush(dp, requests[idx][1])\n                idx += 1\n            repeated.append(len(dp))\n        return sum([x*y for x,y in zip(sorted(nums), sorted(repeated))])%(10**9 + 7)\n", "class Solution:\n    import heapq\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort(reverse=True)\n        res=[[] for i in range(len(nums))]\n        heap=[]\n        for request in requests:\n            res[request[0]].append(request[1])\n        countNum=[0]*len(nums)\n        for i in range(len(res)):\n            if res[i]:\n                for element in res[i]:\n                    heapq.heappush(heap,element)\n            countNum[i]+=len(heap)\n            while heap and heap[0]==i:\n                heapq.heappop(heap)\n        countNum.sort(reverse=True)\n        count=0\n        for i in range(len(nums)):\n            count+=(nums[i]*countNum[i])%(10**9+7)\n        return count%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10 ** 9 + 7\n        n = len(nums)\n        \n        events = []\n        OPEN = -1\n        CLOSE = 1\n        for u, v in requests:\n            events.append([u, OPEN])\n            events.append([v, CLOSE])\n        events.sort()\n        weights = [0] * n\n        \n        open_events = 0\n        nxt_event = 0\n        \n        for i in range(n):\n            # open here\n            while nxt_event < len(events) and events[nxt_event][0] <= i:\n                if events[nxt_event][1] == OPEN:\n                    open_events += 1\n                else:\n                    break\n                nxt_event += 1\n            # compute weight\n            weights[i] = open_events\n            # close here\n            while nxt_event < len(events) and events[nxt_event][0] <= i:\n                if events[nxt_event][1] == CLOSE:\n                    open_events -= 1\n                nxt_event += 1\n\n        return sum([w * num for w,num in zip(sorted(weights), sorted(nums)) ]) % MOD\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        dp = [0] * (len(nums)+1)\n        \n        for r in requests:\n            dp[r[0]] += 1\n            dp[r[1]+1] -= 1\n            \n        counts = [0] * len(nums)\n        counts[0] = dp[0]\n        for i in range(len(nums)):\n            counts[i] = counts[i-1] + dp[i]\n            \n        # print(counts)\n        nums.sort()\n        counts.sort()\n        \n        ans = 0\n        for n, c in zip(nums, counts):\n            ans += n*c\n        \n        return ans % (10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:\n        ends = []\n        for s, e in r: ends.extend([(s, 1), (e+1, -1)])                    \n        ends.sort(reverse=True)\n        n, op = len(a), 0        \n        cnt = [0] * n\n        for i in range(n):               \n            while ends and ends[-1][0] == i: op += ends.pop()[1]                         \n            cnt[i] = op  \n        return sum(x*y for x, y in zip(sorted(cnt), sorted(a))) % (10**9 + 7)", "class Solution:\n        def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n            n = len(nums)\n            arr = [0]*(n+1) # add extra element for handel n+1 case\n            for i, j in requests:\n                arr[i]  += 1\n                arr[j+1] -= 1\n            for i in range(1, n+1):\n                arr[i] += arr[i-1]\n            arr = arr[:n] # remove extra element\n            nums.sort()\n            arr.sort()\n            ans = 0\n            for i in range(n):\n                ans += nums[i] * arr[i]\n            return(ans%(10**9+7))\n", "from typing import List\nimport collections\nimport heapq\nimport itertools\nimport bisect\n\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        s = sorted([a for a, _ in requests])\n        e = sorted([a for _, a in requests])\n        freq = []\n        for i in range(len(nums)):\n            start_after = bisect.bisect_right(s, i)\n            end_before = bisect.bisect_left(e, i)\n            # print(start_after, end_before)\n            # in_it = int(start_after == end_before and start_after < len(requests) and )\n            freq.append(start_after - end_before)\n        # print(freq)\n        freq.sort(reverse=True)\n        nums.sort(reverse=True)\n        res = 0\n        for i, f in enumerate(freq):\n            res += int(f * nums[i] % (1e9 + 7))\n        return int(res % (1e9 + 7))\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        ok=[0]*(len(nums)+1)\n        for i in requests:\n            ok[i[0]]+=1\n            ok[i[1]+1]-=1\n        ok=[0]+ok\n        for i in range(1,len(ok)):\n            ok[i]+=ok[i-1]\n        ok=ok[1:-1]  \n        ok.sort(reverse=True)\n        ans=0\n        nums.sort(reverse=True)\n        for i in range(len(nums)):\n            ans+=nums[i]*ok[i]\n        return ans%1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n, MOD= len(nums), 10**9+7\n        count = [0]*(n+1)\n        for s, e in requests:\n            count[s]+=1\n            count[e+1]-=1\n        for i in range(1, n):\n            count[i]+=count[i-1]\n        return sum(a*b for a,b in zip(sorted(count[:n]), sorted(nums)))%MOD", "class Solution:\n    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:\n        r1 = []\n        for s, e in r:            \n            r1.extend([(s, 1), (e, -1)])            \n        r = r1\n        r.sort(reverse=True)\n        op = 0\n        n = len(a)\n        cand = []\n        cur_start = 0        \n        cur_end = -1\n        cnt = [0] * n\n        for i in range(n):   \n            cl = 0\n            while r and r[-1][0] == i:\n                p = r.pop()[1]                \n                op +=  p == 1\n                cl += p == -1\n            cnt[i] = op\n            op -= cl\n        cnt.sort()\n        a.sort()\n        # print(cnt, a)\n        return sum(x*y for x, y in zip(cnt, a)) % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        freqs = [0] * (len(nums) + 1)\n        for s, e in requests:\n            freqs[s] += 1\n            freqs[e + 1] -= 1\n        freqs.pop()\n        f = 0\n        for i, x in enumerate(freqs):\n            f += x\n            freqs[i] = f\n        nums.sort()\n        freqs.sort()\n        result = 0\n        for n, f in zip(nums, freqs):\n            result += f * n\n        return result % 1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        begin = [0] * (n+1)\n        end = [0] * (n+1)\n        for x,y in requests :\n            begin[x] += 1\n            end[y+1] += 1        \n        l = []\n        cnt = 0\n        for i in range(n) :\n            cnt += begin[i] - end[i]\n            l.append(cnt)\n        l.sort()\n        nums.sort()\n        res = 0\n        for i in range(n) :\n            res += l[i] * nums[i]\n        return res % (10**9 + 7)\n                \n", "class Solution:\n    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:\n        ends = []\n        for s, e in r: ends.extend([(s, 1), (e, -1)])                    \n        ends.sort(reverse=True)\n        n, op = len(a), 0        \n        cnt = [0] * n\n        for i in range(n):   \n            cl = 0\n            while ends and ends[-1][0] == i:\n                p = ends.pop()[1]                \n                op +=  p == 1\n                cl += p == -1\n            cnt[i] = op\n            op -= cl\n        cnt.sort(); a.sort()        \n        return sum(x*y for x, y in zip(cnt, a)) % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        counts = [0 for _ in range(n)]\n        for i, j in requests:\n            counts[i] += 1\n            if j + 1 < n:\n                counts[j+1] -= 1\n        \n        for i in range(1, n):\n            counts[i] += counts[i-1]\n        \n        nums.sort()\n        counts.sort()\n        \n        mod = 10 ** 9 + 7\n        r = 0\n        \n        for i in range(n):\n            r += nums[i] * counts[i]\n        \n        return r % mod", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        arr = [0] * n\n        for s, e in requests:\n            arr[s] += 1\n            if e < n - 1:\n                arr[e + 1] -= 1\n        for i in range(1, n):\n            arr[i] += arr[i - 1]\n        nums.sort()\n        res = 0\n        mod = 10**9 + 7\n        for a in sorted(arr, reverse=1):\n            res += a * nums.pop()\n        return res % mod\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        N = len(nums)\n        index_weight = collections.defaultdict(int)\n        for s, e in requests:\n            index_weight[s] += 1\n            index_weight[e + 1] -= 1\n        \n        for i in range(1, N):\n            index_weight[i] += index_weight[i - 1]\n        \n        print(index_weight)\n        \n        sorted_w = sorted(list(index_weight.keys()), key=lambda i: -index_weight[i])\n        sorted_n = sorted(nums, key=lambda n: -n)\n        \n        ans = 0\n        i = 0\n        for idx in sorted_w:\n            if index_weight[idx] > 0:\n                ans += index_weight[idx] * sorted_n[i]\n                i += 1\n        \n        return ans % (10 ** 9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:    \n        MOD = (10 ** 9 + 7)\n        \n        events = []\n        for l, r in requests:\n            events.append((l, 1))\n            events.append((r + 1, -1))\n        events.sort()\n        \n        request_counts = [0 for i in range(len(nums))]\n        j = 0\n        total = 0\n        for i in range(len(request_counts)):\n            while j < len(events) and events[j][0] == i:\n                total += events[j][1]\n                j += 1\n            request_counts[i] = total\n            \n        request_counts.sort()\n        nums.sort()\n        \n        result = 0\n        for r, n in zip(request_counts, nums):\n            result = (result + r * n) % MOD\n            \n        return result\n        \n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        freq = [0]*(len(nums)+1)\n        \n        for a,b in requests:\n            freq[a] += 1\n            freq[b+1] -= 1\n            \n        for i in range(1,len(freq)):\n            freq[i] = freq[i]+freq[i-1]\n            \n        freq.sort(reverse = True)\n        nums.sort(reverse = True)\n        ans = 0\n        \n        for i in range(len(nums)):\n            ans += freq[i]*nums[i]\n            \n            \n        return ans%1000000007\n        \n            \n            \n        \n            \n", "from collections import defaultdict\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        # scan line\n        points = []\n        for req in requests:\n            points.append([req[0], 0]) # 0 - start\n            points.append([req[1], 1]) # 1 - end\n            \n        points.sort(key=lambda e:(e[0], e[1]))\n        freqCnt = defaultdict(int)\n\n        pos = None\n        cnt = 0\n        for p in points:     \n            if pos != None:\n                # set right end of current interval depending on current point (start or end)\n                if p[1] == 0:\n                    freqCnt[cnt] += p[0] - pos\n                else:\n                    freqCnt[cnt] += p[0] - pos + 1\n            \n            if p[1] == 0:\n                cnt += 1\n            else:\n                cnt -= 1\n                \n            if cnt == 0:\n                pos = None\n            else:\n                # set left end of next interval depending on current point (start or end)\n                if p[1] == 0:\n                    pos = p[0]\n                else:\n                    pos = p[0] + 1\n            \n        nums.sort(reverse=True)\n        result = 0\n        i = 0\n        for k, v in sorted(list(freqCnt.items()), reverse=True):\n            result += k * sum(nums[i:i+v])\n            i += v\n            \n        return result % (10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n\n        def getFreq():            \n            minVal = sys.maxsize\n            maxVal = 0\n\n            freq = [0 for _ in range(len(nums)+1)]   \n\n            for i in range(len(requests)): \n                low = requests[i][0]  \n                freq[low] = freq[low] + 1\n                high = requests[i][1]  \n                freq[high + 1] = freq[high + 1] - 1\n                if low < minVal:  \n                    minVal = low  \n                if high > maxVal: \n                    maxVal = high  \n                \n                # print(freq)\n            \n            for i in range(minVal+1, maxVal + 2):  \n                freq[i] = freq[i] + freq[i - 1]\n            \n            return freq[:-1]  \n         \n        answer = 0\n        freq = getFreq()\n        # print(freq)\n        freq = sorted(freq)\n        nums = sorted(nums)\n        # print(freq, nums)\n        for i in range(1, len(nums)+1):\n            answer = (answer + (freq[i-1]*nums[i-1])) %(10**9+7)\n        # print('-----------')\n        return answer", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0] * (n + 1)\n        for i, j in requests:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(nums)):\n            res += v * c\n        return res % (10**9 + 7)\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        \n        events = []\n        for s, e in requests:\n            events.append((s, \\\"a\\\"))\n            events.append((e, \\\"b\\\"))\n        events.sort()\n        ne = len(events)\n        depth, stabs = 0, []\n        event_i = 0\n        x, kind = events[0]\n        for i in range(len(nums)):\n            while x <= i and kind == \\\"a\\\" and event_i < ne:\n                depth += 1\n                event_i += 1\n                if event_i >= ne: break\n                x, kind = events[event_i]\n            stabs.append(depth)\n            while x <= i and kind == \\\"b\\\" and event_i < ne:\n                depth -= 1\n                event_i += 1\n                if event_i >= ne: break\n                x, kind = events[event_i]\n        stabs.sort(reverse = True)\n        nums.sort(reverse = True)\n        ans = 0\n        for freq, val in zip(stabs, nums):\n            ans += freq*val\n            ans %= MOD\n        return ans % MOD\n        ", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort()\n        times = [0] * (len(nums) + 1)\n        for a, b in requests:\n            times[a] += 1\n            times[b+1] -= 1\n        for i in range(1, len(times)):\n            times[i] += times[i-1]\n        times.pop()\n        times.sort()\n        return sum(a*b for a, b in zip(times, nums)) % (10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        \n        ctr = collections.Counter()\n        pq = []\n        \n        for s, e in requests:\n            heapq.heappush(pq, (s, 1))\n            heapq.heappush(pq, (e+1, -1))\n        \n        # print(pq)\n        counts = 0\n        for k in range(n):\n            while pq and pq[0][0] == k:\n                counts += heapq.heappop(pq)[1]\n            ctr[k] = counts\n        \n        nums.sort()\n        ans = 0\n        for idx, ct in ctr.most_common():\n            ans += nums.pop() * ct\n        return ans % (10**9+7)\n", "from typing import List\nimport collections\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        sweeplines = []\n        for i,j in requests:\n            sweeplines.append((i,1))\n            sweeplines.append((j+1,-1))\n        sweeplines.sort()\n        sweeplines=collections.deque(sweeplines)\n        freq=0\n        freqs=[]\n        for i in range(len(nums)):\n            while sweeplines and sweeplines[0][0]==i:\n                freq+=sweeplines[0][1]\n                sweeplines.popleft()\n            freqs.append(freq)\n        freqs.sort(reverse=True)\n        nums.sort(reverse=True)\n        ans=sum([freq*num for freq,num in zip(freqs,nums)])\n        return ans%(10**9 + 7)\n            \n\n\n\n\n\n\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        i_count = [0] * N\n\n        for start, end in requests:\n            i_count[start] += 1\n\n            if end + 1 < N:\n                i_count[end + 1] -= 1\n\n        for i in range(1, N):\n            i_count[i] += i_count[i - 1]\n\n        return sum(a * b for a, b in zip(sorted(i_count), sorted(nums))) % 1000000007", "from collections import defaultdict\n\nMOD = int(1e9 + 7) \n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        sorted_nums = sorted(nums, reverse=True)\n        temp = [0 for _ in range(len(nums))]\n        sum_ = 0\n        for r in requests:\n            temp[r[0]] += 1\n            if r[1]+1 < len(nums):\n                temp[r[1]+1] -= 1\n            \n        temp2 = []\n        count = 0\n        for x in temp:\n            count += x\n            temp2.append(count)\n        sorted_counter = sorted(temp2, reverse=True)\n        \n        # print(sorted_nums)\n        # print(len(sorted_nums))\n        # print(temp)\n        # print(len(temp))\n        # print(sorted_counter)\n        \n        for counter in sorted_counter:\n            sum_ += (counter * sorted_nums.pop(0)) % MOD\n        \n        # print(sorted_nums)\n        \n        return sum_ % MOD\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        i_count = Counter()\n        first = float('inf')\n        last = -first\n\n        for start, end in requests:\n            i_count[start] += 1\n            i_count[end + 1] -= 1\n            first = min(first, start)\n            last = max(last, end)\n\n        q = []\n        s = 0\n\n        for p in range(first, last + 1):\n            s += i_count[p]\n            q.append(-s)\n\n        heapq.heapify(q)\n\n        ans = 0\n        nums.sort()\n\n        while q:\n            ans = (ans + nums.pop() * -heapq.heappop(q)) % 1000000007\n\n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        requestCount = defaultdict(int) #Number of request per index\n        \n        #Create a min-heap of the start and end intervals.\n        begHeap = []\n        endHeap = []\n        for req in requests:\n            heapq.heappush(begHeap, req[0])\n            heapq.heappush(endHeap, req[1]+1)\n        \n        poppedCount = 0 #Keeps track of how many intervals we have entered without exiting. (Currently active)\n        for i in range(len(nums)):\n            \n            while begHeap and begHeap[0] <= i:\n                heapq.heappop(begHeap)\n                poppedCount += 1\n                \n            while endHeap and endHeap[0] <= i:\n                heapq.heappop(endHeap)\n                poppedCount -= 1\n                continue\n            requestCount[i] = poppedCount\n        \n        #Then we simply get the highest interval frequency and match with the highest nums\n        sortedRequest = sorted(list(requestCount.items()), key = lambda x: -x[1])\n        nums.sort(key = lambda x: -x)\n        \n        out = 0\n        for n, s in zip(nums, sortedRequest):\n            out += (n*s[1])\n            \n        return out % (pow(10, 9)+7)\n", "MODNUM = 10 ** 9 + 7\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        M = len(requests)\n        ct = [0] * N\n        requests = sorted(requests)\n        i, j = 0, 0\n        used = []\n        \n        for k in range(N):\n            while i < M and k >= requests[i][0]:\n                a, b = requests[i]\n                heappush(used, b)\n                i += 1\n            while len(used) > 0 and k > used[0]:\n                heappop(used)\n\n            ct[k] = len(used)\n            # print(ct, i, j)\n            \n        ct = sorted(ct, reverse=True)\n        nums = sorted(nums, reverse=True)\n        # print(ct)\n        # print(nums)\n        \n        res = 0\n        for n, c in zip(nums, ct):\n            if c == 0:\n                break\n            res += n * c\n            \n        return res % MODNUM\n        \n        \n            \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        s = sorted([a for a, _ in requests])\n        e = sorted([a for _, a in requests])\n        freq = []\n        for i in range(len(nums)):\n            start_after = bisect.bisect_right(s, i)\n            end_before = bisect.bisect_left(e, i)\n            freq.append(start_after - end_before)\n        freq.sort(reverse=True)\n        nums.sort(reverse=True)\n        res = 0\n        for i, f in enumerate(freq):\n            res += int(f * nums[i] % (1e9 + 7))\n        return int(res % (1e9 + 7))", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        nums.sort(reverse=True)\n        N = len(nums)\n        \n        events = [0]*(N + 1)\n        \n        for start, end in requests:\n            events[start] += 1\n            events[end + 1] -= 1\n\n        for i in range(1, len(events)):\n            events[i] += events[i - 1]\n\n        res = 0\n        events.pop()\n\n        events.sort()\n        nums.sort()\n        \n        for num, size in zip(nums, events):\n            res += num*size\n        \n        return res % MOD", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        freqs = [0] * (len(nums) + 1)\n        for s, e in requests:\n            freqs[s] += 1\n            freqs[e + 1] -= 1\n        freqs.pop()\n        f = 0\n        for i, x in enumerate(freqs):\n            f += x\n            freqs[i] = f\n        nums.sort()\n        freqs.sort()\n        result = 0\n        for n, f in zip(nums, freqs):\n            result += f * n\n        return result % 1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        nums.sort()\n        n = len(nums)\n        weights = [0] * n\n        for start, end in requests:\n            weights[start] += 1\n            if end + 1 < n:\n                weights[end+1] -= 1\n        for i in range(1, n):\n            weights[i] += weights[i-1]\n        weights.sort()\n        ans = 0\n        for num, weight in zip(nums, weights):\n            ans += num * weight\n            ans %= MOD\n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        requests.sort(reverse=True)\n        cur = []\n        height = []\n        for i in range(len(nums)):\n            while requests and requests[-1][0] <= i:\n                heapq.heappush(cur, requests.pop()[1])\n            while cur and cur[0] < i:\n                heapq.heappop(cur)\n            height.append(len(cur))\n        print(height)\n        height.sort()\n        nums.sort()\n        return sum(n * h for n, h in zip(nums, height)) % (10 ** 9 + 7)\n\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10 ** 9 + 7\n        \n        tmp = sorted([k for i, j in requests for k in [(i, 1), (j + 1, -1)]])\n        counter = collections.defaultdict(int)\n        last = 0\n        now = 0\n        for ind, delta in tmp:\n            counter[now] += ind - last\n            last = ind\n            now += delta\n        \n        nums.sort(reverse=True)\n        l = len(nums)\n        result = 0\n        now = 0\n        for count, num in sorted(list(counter.items()), reverse=True):\n            result += sum(nums[now: now + num]) * count\n            now += num\n            if now > l:\n                break\n        \n        return result % MOD\n        \n#         nums.sort(reverse=True)\n#         # nums.sort()\n        \n#         starts = collections.deque(sorted(i for i, j in requests))\n#         ends = collections.deque(sorted(j for i, j in requests))\n#         counter = collections.defaultdict(int)\n#         now = 0\n#         prev = 0\n#         while starts or ends:\n#             if starts and ends:\n#                 if starts[0] > ends[0]:\n#                     counter[now] += ends[0] - prev + 1\n#                     now -= 1\n#                     prev = ends[0] + 1\n#                     ends.popleft()\n#                 else:\n#                     counter[now] += starts[0] - prev\n#                     now += 1\n#                     prev = starts[0]\n#                     starts.popleft()\n#             else:\n#                 counter[now] += ends[0] - prev + 1\n#                 now -= 1\n#                 prev = ends[0] + 1\n#                 ends.popleft()\n        \n#         # counter = collections.defaultdict(int)\n#         # for start, end in requests:\n#         #     for i in range(start, end + 1):\n#         #         counter[i] += 1\n#         result = 0\n#         now = 0\n#         for i in sorted(counter, reverse=True):\n#             c = counter[i]\n#             result += sum(nums[now: now + c]) * i\n#             now += c\n#         # for i, j in zip(sorted(counter.values(), reverse=True), nums):\n#             # result += i * j\n#         return result % (10 ** 9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        '''\n        factors = [0]*len(nums)\n        for a,b in requests:\n            for i in range(a,b+1):\n                factors[i] += 1\n        factors.sort()\n        nums.sort()\n        out = 0\n        for i in range(len(nums)):\n            out = (out + nums[i]*factors[i])%(10**9+7)\n        return out\n        '''\n        \n        pts = []\n        for a, b in requests:\n            pts.append((a,-1))\n            pts.append((b,+1))\n        pts.sort()\n        dic = defaultdict(int)\n        factor, prev = 0, 0\n        for a, d in pts:\n            if d == -1:\n                dic[factor] += (a-prev)\n                prev = a\n            else:\n                dic[factor] += (a+1-prev)\n                prev = a+1\n            factor += -d\n        nums.sort(reverse=True)\n        prev, out = 0, 0\n        dic = sorted(list(dic.items()), key=lambda x: x[0], reverse=True)\n        for factor, length in dic:\n            for k in range(prev, prev + length):\n                out = (out + factor*nums[k])%(10**9 + 7)\n            prev += length\n        return out\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10 ** 9 + 7\n        ranks = [0] * (len(nums) + 1)\n        requests.sort()\n        \n        for start, end in requests:\n            ranks[start] += 1\n            ranks[end + 1] -= 1\n        \n        nums.sort()\n        for i in range(1, len(nums) + 1):\n            ranks[i] += ranks[i - 1]\n        \n        ranks = ranks[:len(nums)]\n        \n        return sum(x * y for x, y in zip(sorted(nums), sorted(ranks))) % MOD", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        '''\n        Tricky part is finding the permutation that will result in maximum\n        sum of the requests\n        \n        Looping through all permutations will likely TLE\n        \n        Setup nums in a way such that requests is maximized.\n        \n        Do it in greedy way + sort\n        Have the max values be at the largest request interval\n        \n        How to deal with overlapping requests\n        \n        Largest number goes in index with most\n        overlappings, second largest goes to index\n        with second most overlappings etc.\n        \n          -\n          - - -\n        - - -\n        0 1 2 3 4 5\n        1 2 3 4 5 9\n         \n        requests\n        [[0,2],[1,3],[1,1]]\n        \n        overlaps\n        \n        0 1 2 3 4 5\n        1 3 2 1 0 0\n        \n        1 2 0 3 4 5\n        3 2 1 1 0 0\n        \n        0 1 2 3 4 5\n        4 9 5 3 2 1\n        \n        For each index calculate the number of request that overlap it\n        Better to do this the other way around.\n        \n        This still TLEs\n        \n        O(nlogn)\n        \n        Your implementation is not actually O(nlogn) see\n        comment in code\n        '''\n        if not nums or not requests: return 0\n        \n        overlaps = [(i, 0) for i in range(len(nums) + 1)]\n        for start, end in requests:\n            overlaps[start] = (overlaps[start][0], overlaps[start][1] + 1)\n            overlaps[end + 1] = (overlaps[end + 1][0], overlaps[end + 1][1] - 1)\n            \n        for i in range(1, len(overlaps)):\n            overlaps[i] = (overlaps[i][0] , overlaps[i][1] + overlaps[i - 1][1])\n        \n        overlaps.pop()\n        overlaps.sort(key=lambda tup: tup[1], reverse=True)\n        nums.sort()\n        max_permutation = [0] * len(nums)\n        for i, freq in overlaps:\n            max_permutation[i] = nums[-1]\n            nums.pop()\n        \n        prefix_sum = [max_permutation[0]]\n        for i in range(1, len(max_permutation)):\n            prefix_sum.append(prefix_sum[i - 1] + max_permutation[i])\n        \n        sum = 0\n        for start, end in requests:\n            right = prefix_sum[end]\n            left = 0 if start == 0 else prefix_sum[start - 1]\n            sum += right - left\n        \n        return sum % (10**9 + 7)\n\n    \n    def maxSumRangeQuery_1(self, nums: List[int], requests: List[List[int]]) -> int:\n        '''\n        Discuss Solution thats faster at detecting\n        the number of requests that overlap an index.\n        \n        Key Idea have array t, loop\n        through requests [[start, end] ...]\n        \n        Make t[start] += 1 to indicate\n        every index after start is counted once\n        for this request overlap\n        Make t[end + 1] -= 1 to indicate\n        every index after end + 1 is counted one less\n        for this request overlap\n        \n        The prefix sum of array t tells us\n        the number of requests that overlap\n        an index\n        \n        requests\n        [[0,2],[1,3],[1,1]]\n        \n          -\n          - - -\n        - - -\n        0 1 2 3 4 5\n        1 2 3 4 5 9\n        \n        t\n        0  1  2  3  4  5  6\n        1  2 -1 -1 -1\n        \n        t_prefix\n        0  1  2  3  4  5  6\n        1  3  2  1  0  0  0\n        \n        t.pop to remove index 6\n        Sort both nums and t and\n        use zip to line them up\n        This matches most frequently\n        overlapped index with biggest\n        num.\n        \n        nums\n        1 2 3 4 5 9\n        t\n        0 0 1 1 2 3\n        \n        Multiply because index i gets overlapped\n        t[i] times so the nums value of mapping\n        also gets mulitplied that number of times\n        for the sum\n        \n        nums[i] * t[i]\n        0 0 3 4 10 27\n        \n        sum of final = 44\n        '''\n        t = [0] * (len(nums) + 1)\n        \n        for start, end in requests:\n            t[start] += 1\n            t[end + 1] -= 1\n            \n        for i in range(1, len(nums)):\n            t[i] += t[i - 1]\n        \n        nums.sort()\n        t.pop() # Makes it so t matches length with nums\n        t.sort()\n\n        return sum(a*b for a, b in zip(nums, t)) % (10**9 + 7)\n            \n        \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        len_nums = len(nums)\n        frequencies = [0] * (len_nums + 1)\n        for start, end in requests:\n            frequencies[start] += 1\n            frequencies[end + 1] -= 1\n        for k in range(1, len_nums):\n            frequencies[k] += frequencies[k - 1]\n        frequencies.sort(reverse=True)\n        nums.sort(reverse=True)\n        max_sum = 0\n        for num, frequency in zip(nums, frequencies):\n            max_sum += num * frequency\n        return max_sum % (10**9 + 7)\n", "class Solution:\n    \n    def update(self,d,s,e):\n        d[s]+=1\n        d[e+1]-=1\n        \n        \n        \n        \n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort()\n        n=len(nums)\n        d=[0]*(n+1)\n        m=10**9+7\n        for i in range(len(requests)):\n            s=requests[i][0]\n            e=requests[i][1]\n            self.update(d,s,e)\n                \n     \n\n        for i in range(0,n):\n            if i==0:\n                continue\n            else:\n                d[i]=d[i]+d[i-1]\n                \n        d.pop()\n                \n        d.sort()\n        \n        count=0\n        for i in range(n):\n            count=(count+d[i]*nums[i])%m\n            \n        return count%m\n        \n        \n", "class Solution:\n    def maxSumRangeQuery(self, A: List[int], E: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        cts = collections.Counter()\n        for a,b in E:\n            cts[a] += 1\n            cts[b+1] -= 1\n        N = len(A)\n        for i in range(N):\n            cts[i] += cts[i-1]\n        X = [(i, cts[i]) for i in range(N)]\n        X.sort(key = lambda a: a[1])\n        A.sort()\n        res = [0]*N\n        for i in range(N):\n            res[X[i][0]] = A[i]\n        hardproblem = [0]\n        for a in res:\n            hardproblem.append(hardproblem[-1] + a)\n        total = 0\n        for a,b in E:\n            total = ( total + hardproblem[b+1] - hardproblem[a]) % MOD\n        return total", "from itertools import permutations\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort(reverse=True)\n        count = [0 for i in range(len(nums) + 1)]\n        for start, end in requests:\n            count[start] += 1\n            count[end + 1] -= 1\n        for i in range(1, len(count)):\n            count[i] += count[i - 1]\n        count.sort(reverse=True)\n        maxSum = 0\n        for i in range(len(count) - 1):\n            maxSum += count[i] * nums[i]\n        return maxSum % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10 ** 9 + 7\n        weights = defaultdict(int)\n        requests.sort()\n        prev, ends = None, []\n        for l, r in requests:\n            while ends and ends[0] < l:\n                weight = len(ends)\n                end = heappop(ends)\n                weights[weight] += (end - prev) + 1\n                prev = end + 1\n                \n            if not ends:\n                prev = l\n                ends = [r]\n            else:\n                weight = len(ends)\n                weights[weight] += (l - prev)\n                prev = l\n                heappush(ends, r)\n                \n        while ends:\n            weight = len(ends)\n            end = heappop(ends)\n            weights[weight] += (end - prev) + 1\n            prev = end + 1  \n        \n        total = 0\n        nums.sort(reverse=True)\n        l = 0\n        for weight in sorted(list(weights.keys()), reverse=True):\n            length = weights[weight]\n            total += (sum(nums[l: l + length]) * weight) % MOD\n            l = l + length\n        return total % MOD\n            \n                \n", "import heapq\nimport math\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        starts = []\n        ends = []\n        \n        for start, end in requests:\n            heapq.heappush(starts, (start, end))\n        \n        curr_start = None\n        new_ranges = []\n        \n        while len(starts) > 0:\n            peek_start = starts[0]\n            \n            peek_end = ends[0] if len(ends) > 0 else (math.inf, math.inf)\n            if peek_end[0] < peek_start[0]:\n                new_ranges.append((curr_start, peek_end[0], len(ends)))\n                while len(ends) > 0 and ends[0][0] == peek_end[0]:\n                    heapq.heappop(ends)\n                curr_start = peek_end[0] + 1\n            elif peek_end[0] > peek_start[0]:\n                if len(ends) > 0:\n                    new_ranges.append((curr_start, peek_start[0] - 1, len(ends)))\n                while len(starts) > 0 and starts[0][0] == peek_start[0]:\n                    elt = heapq.heappop(starts) \n                    heapq.heappush(ends, (elt[1], elt[0]))\n                curr_start = peek_start[0]\n            else:\n                new_ranges.append((curr_start, peek_end[0] - 1, len(ends)))\n                \n                while len(starts) > 0 and starts[0][0] == peek_start[0]:\n                    elt = heapq.heappop(starts) \n                    heapq.heappush(ends, (elt[1], elt[0]))\n                \n                new_ranges.append((peek_end[0], peek_end[0], len(ends)))\n                \n                while len(ends) > 0 and ends[0][0] == peek_end[0]:\n                    heapq.heappop(ends)  \n                \n                curr_start = peek_end[0] + 1\n         \n        while len(ends) > 0:\n            peek_end = ends[0]\n            new_ranges.append((curr_start, peek_end[0], len(ends)))\n            while len(ends) > 0 and ends[0][0] == peek_end[0]:\n                heapq.heappop(ends)\n            curr_start = peek_end[0] + 1\n           \n        counts = [0] * len(nums)\n        for start, end, f in new_ranges:\n            for i in range(start, end + 1):\n                counts[i] += f  \n        sorted_indices = sorted(counts)\n        sorted_elts = sorted(nums)\n        \n\n        res = 0\n        while len(sorted_elts) > 0:\n            res += sorted_elts.pop() * sorted_indices.pop()\n        return res % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort()\n        dp = [0] *(len(nums) + 1)\n        for x,y in requests:\n            dp [x] += 1 \n            dp [y +1] -= 1\n        \n        for i in range(1,len(nums) + 1 ):\n            dp[i] += dp[i-1]\n         \n        res = 0\n        for v, c in zip(sorted(dp[:-1]), sorted(nums)):\n            res += v * c\n        return res % (10**9 + 7)\n    \n    # 0,1,2,1,1,0\n    # 0 1,0,0,-1,0\n    # 1,0,1,0,-1,0\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mod=10**9+7\n        n=len(nums)\n        ops=[]\n        for request in requests:\n            ops.append((request[0],1))\n            ops.append((request[1]+1,-1))\n        ops.sort()\n        nums.sort()\n        counts=[]\n        cur=0\n        count=0\n        for idx in range(n):\n            while cur<len(ops) and idx==ops[cur][0]:\n                count+=ops[cur][1]\n                cur+=1\n            counts.append(count)\n        counts.sort()\n        return sum([c*num for c,num in zip(counts,nums)]) % mod", "from collections import deque\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        counter = [0] * n\n        enter = list()\n        leave = list()\n        for l, r in requests:\n            enter.append(l)\n            leave.append(r)\n        \n        enter.sort()\n        leave.sort()\n        \n        ei = 0\n        li = 0\n        en = len(requests)\n        cnt = 0\n        for i in range(n):\n            while ei < en and enter[ei] == i:\n                ei += 1\n                cnt += 1\n            counter[i] = cnt\n            while li < en and leave[li] == i:\n                li += 1\n                cnt -= 1\n        #print(counter)\n        \n        vals = []\n        for i, cnt in enumerate(counter):\n            vals.append([-cnt, i])\n        vals.sort()\n        #print(vals)\n        \n        res = 0\n        nums.sort()\n        for i, num in enumerate(nums[::-1]):\n            res -= num * vals[i][0]\n            res = res % (10**9+7)\n        # for val, num zip(vals, nums[::-1]):\n        #     res += num * (-val[0])\n        return res\n            \n                    \n                    \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10 **9 + 7\n        n = len(nums)\n        count = [0] * (n)\n        for s, e in requests:\n            count[s] += 1\n            if e + 1 < n:\n                count[e + 1] -= 1\n        for i in range(1, n):\n            count[i] += count[i-1]\n        count.sort()\n        nums.sort()\n        ans = 0\n        for c, a in zip(count, nums):\n            ans = (ans + c * a) % MOD\n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort()\n        n = len(nums)\n        bit = [0] * (n + 1)\n        def query(i):\n            s = 0\n            while i > 0:\n                s += bit[i]\n                i -= (i & -i)\n            return s\n        \n        def insert(key, value):\n            while key <= n:\n                bit[key] += value\n                key += (key & -key)\n        \n        for request in requests:\n            insert(request[0] + 1, 1)\n            insert(request[1] + 2, -1)\n        \n        vals = sorted([query(i + 1) for i in range(n)])\n        return sum(x * y for x, y in zip(vals, nums)) % 1_000_000_007\n    \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        counts = [0] * 100001\n        for start, end in requests:\n            counts[start] += 1\n            counts[end + 1] -= 1\n        for i in range(100001):\n            counts[i] += counts[i-1]\n        result, mod = 0, 10 ** 9 + 7\n        for num, count in zip(sorted(nums, reverse=True), sorted(counts, reverse=True)):\n            result = (result + num * count) % mod\n        return result\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        c = [0] * n\n        a = [0] * n\n        b = [0] * n\n        for x in requests:\n            a[x[0]] += 1\n            b[x[1]] += 1\n        now = 0\n        for i in range(n):\n            now += a[i]\n            c[i] = now\n            now -= b[i]\n        c.sort()\n        nums.sort()\n        ret = 0\n        for i in range(n):\n            ret += c[i] * nums[i]\n        ret %= 10 ** 9 + 7\n        return ret", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        start_dic, end_dic = {}, {}\n        modd = 10**9 + 7\n        for req in requests:\n            st, ed = req\n            start_dic[st] = start_dic.get(st, 0) + 1\n            end_dic[ed] = end_dic.get(ed, 0) + 1\n        \n        idx_cnt = []\n        cnt = 0\n        for i in range(n):\n            if i in start_dic:\n                cnt += start_dic[i]\n            if i-1 in end_dic:\n                cnt -= end_dic[i-1]\n            idx_cnt.append(cnt)\n        \n        idx_cnt.sort()\n        nums.sort()\n        \n        res = [idx_cnt[i]*nums[i] for i in range(n)]\n        ans = 0\n        for x in res:\n            ans = (ans + x) % modd\n        return ans\n        \n        # ele[0]*ele[1] for ele in zip([idx_cnt, nums])\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        request_counts = [0] * (len(nums) + 1)\n        \n        for start, end in requests:\n            request_counts[start] += 1\n            request_counts[end + 1] -= 1\n        \n        cur_count = 0\n        for i in range(len(nums) + 1):\n            cur_count += request_counts[i]\n            request_counts[i] = cur_count\n        \n        nums.sort(reverse=True)\n        \n        sorted_idxs = sorted(range(len(nums) + 1), key=lambda i: request_counts[i], reverse=True)\n        \n        # perm = [0] * len(nums)\n        ans = 0\n        \n        for idx, num in zip(sorted_idxs, nums):\n            ans += num * request_counts[idx]\n        \n        return ans % int(1e9 + 7)    ", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        req=[0]*(len(nums)+1)\n        # Adding 1 for all elements in req(r[0]:r[1]+1) costs too much time.\n        for r in requests:\n            req[r[0]]+=1\n            req[r[1]+1]-=1\n        for i in range(1,len(req)):\n            req[i]+=req[i-1]\n        req=sorted(req, reverse=True)\n        nums=sorted(nums, reverse=True)\n        answer=0\n        for i in range(len(nums)):\n            if req[i]==0 or nums[i]==0:\n                return answer%1000000007\n            answer+=req[i]*nums[i]\n        return answer%1000000007", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \\\"\\\"\\\"\n        Assume:\n        1. list, list -> int\n        2. only find sum, permutation is not unique\n        3. nums is not sorted\n        \n        \n        Algorithm:\n        sort nums\n        \n        in requests, count number of coverage for each index. \n        counts = [c0, c1]\n        put (c0, 0), (c1, 1) into maxHeap\n        popout maxHeap, each index gets the assigned element from largest to smallest to form new nums\n        \n        calculate sum of requests in new nums\n        \n        Complexity:\n        time: max(O(nlogn), O(mn))\n        space: O(n)\n        \n        Follow up:\n        1. use LinkedHashMap\n        2. \n        \n        \\\"\\\"\\\"\n        if not nums:\n            return -1 # rise IllegalInputArgumentException\n        \n        MOD = 10 ** 9 + 7\n        result, n, m = 0, len(nums), len(requests)\n        counts = [0 for _ in range(n)]\n        max_heap = []\n        \n        # O(m*n)\n        #for i in range(m):\n        #    for j in range(requests[i][0], requests[i][1] + 1):\n        #        counts[j] += 1\n                \n        # O(max(m, n)): use sweep line\n        records = []\n        for i in range(m):\n            records.append([requests[i][0], 1])\n            records.append([requests[i][1]+1, -1])\n        for index, delta in sorted(records):\n            if index < n:\n                counts[index] += delta\n        for i in range(n):\n            if i != 0:\n                counts[i] = counts[i] + counts[i-1]\n        \n        for i in range(n):\n            heapq.heappush(max_heap, (-counts[i], i))\n        \n        # O(nlogn)\n        nums.sort()\n        new_nums, cur_max = [0 for _ in range(n)], n - 1\n        while max_heap and cur_max >= 0:\n            cur = heapq.heappop(max_heap)\n            new_nums[cur[1]] = nums[cur_max]\n            cur_max -= 1\n        \n        prefixsum = [0 for _ in range(n)]\n        for i in range(n):\n            if i == 0:\n                prefixsum[i] = new_nums[i]\n            else:\n                prefixsum[i] = prefixsum[i-1] + new_nums[i]\n        # print(f'counts:{counts}, new_nums:{new_nums}')\n        for i in range(m):\n            result += prefixsum[requests[i][1]] - prefixsum[requests[i][0]] + new_nums[requests[i][0]]\n        return result % MOD\n        \n        \n        \n        ", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        imos = [0] * (n + 1)\n        for l, r in requests:\n            imos[l] += 1\n            imos[r + 1] -= 1\n        for i in range(n):\n            imos[i + 1] += imos[i]\n        del imos[-1]\n        \n        ans = 0\n        for i, v in zip(sorted(nums), sorted(imos)):\n            ans += i * v\n            ans %= 10 ** 9 + 7\n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], req: List[List[int]]) -> int:\n        l=[0]*(len(nums)+1)\n        nums.sort(reverse=True)\n        for i in req:\n            l[i[0]]+=1\n            l[i[1]+1]-=1\n        for i in range(1,len(l)):\n            l[i]+=l[i-1]\n        l=l[:-1]    \n        #print(l)        \n        d=collections.defaultdict(list)\n        for i in range(len(l)):\n            d[l[i]].append(i)\n        di=collections.OrderedDict(sorted(d.items()))   \n        #print(di)\n        k=0\n        ans=[0]*len(nums)\n        for i in di:\n            for j in di[i]:\n                ans[j]=nums[len(nums)-k-1]\n                k+=1\n        #return ans        \n        c=0\n        print(ans)    \n        for i in range(1,len(ans)):\n            ans[i]+=ans[i-1]\n        \n        ans.insert(0,0)\n        print(ans)   \n        for i in req:\n            c+=(ans[i[1]+1]-ans[i[0]])\n        return c%(10**9+7)\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        m = len(requests)\n        d = [0] * len(nums)\n        # R = sorted(requests, key = lambda x:(x[0],-x[1]))\n        R = sorted(requests)\n        q = []\n        j = 0\n        for i in range(n):\n            while q and q[0] < i:\n                heapq.heappop(q)\n            while j < m and R[j][0] <= i:\n                heapq.heappush(q, R[j][1])\n                j += 1\n            d[i] = len(q)\n        \n        # print(d)\n        \n        # d.sort(reverse=1)\n        # nums.sort(reverse=1)\n        # ret = 0\n        # j = 0\n        # for i in d:\n        #     ret += i * nums[j]\n        #     j += 1\n        # return ret % (10 ** 9 + 7)\n        \n        d.sort()\n        nums.sort()\n        ret = 0\n        for i,j in zip(nums,d):\n            ret += i*j\n        return ret % (10 ** 9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        fq = [0]*n\n        for l,r in requests:\n            fq[l]+=1\n            if r<n-1:\n                fq[r+1]-=1\n        for i in range(n):\n            fq[i]=(fq[i-1] if i!=0 else 0)+fq[i]\n        nums.sort()\n        fq.sort()\n        ans = 0\n        for v,z in zip(nums,fq):\n            ans = (ans+v*z)%(10**9+7)\n        return ans\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0 for _ in range(n)]\n        h = []\n        requests.sort(key = lambda x: x[0])\n        requests.append([float('inf'),float('inf')])\n        cur = 0\n        for s,e in requests:\n            while h and h[0] < s:\n                #all intervals in heap share [cur, h[0]]\n                for i in range(cur, h[0]+1):\n                    count[i] += len(h)\n                cur = h[0]+1\n                heapq.heappop(h)\n            if s != float('inf'):\n                for i in range(cur, s):\n                    count[i] += len(h)\n                cur = s\n                heapq.heappush(h,e)\n        mod = 10**9+7\n        return sum([c*v for c,v in zip(sorted(nums),sorted(count))])%mod\n                \n                    \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        take = [False] * N\n        MOD = 10**9 + 7\n        \n        fenwick = [0] * (N+1)\n        \n        def add(idx, val):\n            idx += 1  # Make 1 based index\n            while idx <= N:\n                fenwick[idx] += val\n                idx += idx & -idx\n            \n        \n        def sum_(idx):\n            idx += 1  # Make 1 based index\n            ans = 0\n            \n            while idx > 0:\n                ans += fenwick[idx]\n                idx -= idx & -idx\n            return ans\n        \n        def range_sum(a, b):\n            return sum_(b) - sum_(a-1)\n        \n        for a, b in requests:\n            # Make one based index\n            add(a, 1)\n            add(b+1, -1)\n        \n        occurrences = [0] * N\n        \n        for i in range(N):\n            occurrences[i] = sum_(i)\n        \n        occ = sorted([(v,i) for i, v in enumerate(occurrences)], reverse=True)\n        nums.sort()\n        \n        ans = 0\n        for a, b in occ:\n            if a:\n                ans += (nums.pop() * a)\n        \n        \n        return ans%MOD\n        \n                \n    \n    \n#         vector<int> bit;  // binary indexed tree\n#     int n;\n\n#     FenwickTreeOneBasedIndexing(int n) {\n#         this->n = n + 1;\n#         bit.assign(n + 1, 0);\n#     }\n\n#     FenwickTreeOneBasedIndexing(vector<int> a)\n#         : FenwickTreeOneBasedIndexing(a.size()) {\n#         for (size_t i = 0; i < a.size(); i++)\n#             add(i, a[i]);\n#     }\n\n#     int sum(int idx) {\n#         int ret = 0;\n#         for (++idx; idx > 0; idx -= idx & -idx)\n#             ret += bit[idx];\n#         return ret;\n#     }\n\n#     int sum(int l, int r) {\n#         return sum(r) - sum(l - 1);\n#     }\n\n#     void add(int idx, int delta) {\n#         for (++idx; idx < n; idx += idx & -idx)\n#             bit[idx] += delta;\n#     }\n", "from collections import defaultdict as dd\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        nums.sort()\n        n = len(nums)\n        d = dd(int)\n        new = [0]*n\n        \n        for r in requests :\n            s, e = r\n            new[s] += 1\n            if e+1<n :\n                new[e+1] -= 1\n        c = 0\n        for i in range(n) :\n            \n            new[i] += c\n            c = new[i]\n            \n        new.sort()\n        ans = 0\n        for n in new[::-1] :\n            ans = (ans +(n*nums[-1])% (10**9 + 7)) % (10**9 + 7)\n            nums.pop()\n        return ans \n", "import collections\nimport heapq\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        heapq.heapify(requests)\n        count, end_heap, counter = 0, [], collections.Counter()\n        for i in range(len(nums)):\n            while requests and i >= requests[0][0]:\n                count += 1\n                heapq.heappush(end_heap, heapq.heappop(requests)[1])\n            while end_heap and i > end_heap[0]:\n                heapq.heappop(end_heap)\n                count -= 1\n            counter[i] += count\n        heap = [-num for num in nums]\n        heapq.heapify(heap)\n        total, mod = 0, 10 ** 9 + 7\n        for counts in sorted(list(counter.values()), reverse=True):\n            total = (total - heapq.heappop(heap) * counts) % mod\n        return total\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        freq = [0] * (n + 1)\n        \n        for i, j in requests:\n            freq[i] += 1\n            freq[j+1] -= 1\n            \n        for i in range(1, n + 1):\n            freq[i] += freq[i - 1]\n        freq = freq[:-1]    \n        freq.sort()\n        nums.sort()\n        result = 0\n        for i in range(n):\n            result += freq[i] * nums[i]\n        return result % 1_000_000_007", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        N = len(nums)\n        index_weight = collections.defaultdict(int)\n        for s, e in requests:\n            index_weight[s] += 1\n            index_weight[e + 1] -= 1\n        \n        for i in range(1, N + 1):\n            index_weight[i] += index_weight[i - 1]\n        \n        sorted_w = sorted(list(index_weight.keys()), key=lambda i: -index_weight[i])\n        sorted_n = sorted(nums, key=lambda n: -n)\n        \n        ans = 0\n        i = 0\n        for idx in sorted_w:\n            if index_weight[idx]:\n                ans += index_weight[idx] * sorted_n[i]\n                i += 1\n        \n        return ans % (10 ** 9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        nums.sort()\n        counter = [0] * (10 ** 5 + 2)\n        \n        for start, end in requests:\n            counter[start] += 1\n            counter[end+1] -= 1\n        \n        for i in range(1, len(counter)):\n            counter[i] += counter[i-1]\n        \n        counter.sort()\n        \n        p1 = len(counter) - 1\n        p2 = len(nums) - 1\n        count = 0\n        while counter[p1] > 0:\n            count = (count + counter[p1] * nums[p2]) % (10**9+7)\n            p1 -= 1\n            p2 -= 1\n        \n        return count", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        nums.sort(reverse=True)\n        \n        index=[0]*len(nums)\n        for start,end in requests:\n            index[start]+=1\n            if (end+1)<len(nums):\n                index[end+1]-=1\n            \n        for i in range(1,len(nums)):\n            index[i]+=index[i-1]\n        \n        \n        index.sort(reverse=True)\n        \n        result=0\n        for i in range(len(index)):\n            freq=index[i]\n            value=nums[i]\n            \n            if freq==0:\n                break\n            result+=value*freq\n            \n        return result%(10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        nums.sort(reverse=True)\n        reqs = defaultdict(int)\n        for start, end in requests:\n            reqs[start] += 1\n            reqs[end + 1] -= 1\n        counts = defaultdict(int)\n        h = 0\n        last = -1\n        for i in sorted(reqs.keys()):\n            if h > 0:\n                counts[h] += max(0, i - last)\n            h += reqs[i]\n            last = i\n        res = 0\n        i = 0\n        n = len(nums)\n        for h, c in sorted(list(counts.items()), reverse=True):\n            for j in range(c):\n                if i == n:\n                    break\n                num = nums[i]\n                res += num * h\n                res %= MOD\n                i += 1\n            if i == n:\n                break\n        return res\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        reqdict = collections.Counter()\n        for request in requests:\n            reqdict[request[0]] += 1\n            reqdict[request[1]+1] -= 1\n            \n        increments = []\n        prev = None\n        mult = 0\n        for key in sorted(reqdict.keys()):\n            #print([key, reqdict[key]])\n            if reqdict[key] != 0:\n                if prev != None:\n                    increments.append([mult, key-prev])\n                prev = key\n                mult += reqdict[key]\n                \n        increments.sort()\n        #print(increments)\n        \n        x = len(increments)-1\n        ans = 0\n        nums.sort()\n        for i in range(len(nums)-1, -1, -1):\n            #print([nums[i], increments[x][0]])\n            if x >= 0 and increments[x][0] > 0:\n                ans = (ans + nums[i] * increments[x][0]) % (10**9 + 7)\n                \n            increments[x][1] -= 1\n            if increments[x][1] == 0:\n                x -= 1\n                \n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n=len(nums)\n        ind_counts=[0]*n\n        nums2=ind_counts.copy()\n        for i,j in requests:\n            ind_counts[i]+=1\n            if j+1<n:\n                ind_counts[j+1]-=1\n        for i in range(1,n):ind_counts[i]+=ind_counts[i-1]\n        nums,ind_count=sorted(nums,reverse=True),sorted(list(range(n)),key=lambda x: -ind_counts[x])\n        #print(ind_count)\n        i=0\n        while i<n and ind_counts[ind_count[i]]>0:\n            nums2[ind_count[i]]=nums.pop(0)\n            i+=1\n        #print(nums2)\n        ans=0\n        for i in range(1,n):\n            nums2[i]+=nums2[i-1]\n        for i,j in requests:\n            ans+=nums2[j]-nums2[i-1] if i-1>=0 else nums2[j]\n        return ans%1000000007", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n=len(nums)\n        rng=[0]*(n+1)\n        for req in requests:\n            l,r=req\n            rng[l],rng[r+1]=rng[l]+1,rng[r+1]-1\n        lst=[]\n        for i in range(n):\n            if i:\n                rng[i]+=rng[i-1]\n            lst.append(rng[i])\n        # print(rng)\n        # print(lst)\n            \n        ans=0\n        return sum(num*cnt for num,cnt in zip(sorted(nums, reverse=True),sorted(lst, reverse=True)))%1000000007\n", "from bisect import bisect_left as bl, bisect_right as br\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        arr=[]\n        for i in range(len(requests)):\n            arr.append((requests[i][0],-1))\n            arr.append((requests[i][1],1))\n        arr.sort()\n        freq=[0]*len(nums)\n        j=0\n        s=0\n        for i in range(len(nums)):\n            while(j<len(arr) and arr[j][0]==i and arr[j][1]==-1):\n                s+=1\n                j+=1\n            freq[i]=s\n            while(j<len(arr) and arr[j][0]==i and arr[j][1]==1):\n                s-=1\n                j+=1\n        freq.sort(reverse=True)\n        nums.sort(reverse=True)\n        ans=0\n        for i in range(len(nums)):\n            ans+=(freq[i]*nums[i])%(10**9+7)\n        \n        return ans%(10**9+7)\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mod = 10**9+7\n        n = len(nums)\n        \n        freq = [0]*n\n        for start, end in requests:\n            freq[start] += 1\n            if end+1 < n:\n                freq[end+1] -= 1\n        \n        cur = 0\n        for i in range(len(freq)):\n            cur += freq[i]\n            freq[i] = cur\n        \n        freq.sort(reverse = True)\n        nums.sort(reverse = True)\n        return sum([freq[i]*nums[i] for i in range(n)]) % mod", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        nums.sort()\n        counter = [0] * (10 ** 5 + 2)\n        \n        for start, end in requests:\n            counter[start] += 1\n            counter[end+1] -= 1\n        \n        for i in range(1, len(counter)):\n            counter[i] += counter[i-1]\n        \n        counter.sort()\n        \n        p1 = len(counter) - 1\n        p2 = len(nums) - 1\n        count = 0\n        while counter[p1] > 0:\n            count = (count + counter[p1] * nums[p2]) \n            p1 -= 1\n            p2 -= 1\n        \n        return count % (10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        requests.sort()\n        ct = []\n        heap = []\n        for i in range(len(nums)):\n            while len(requests) != 0 and requests[0][0] == i:\n                heapq.heappush(heap, requests[0][1])\n                requests.pop(0)\n            while len(heap) != 0 and heap[0] < i:\n                heapq.heappop(heap)\n            ct.append(len(heap))\n        ct.sort(reverse=True)\n        nums.sort()\n        j = ans = 0\n        for i in range(len(nums) - 1, -1, -1):\n            ans += nums[i] * ct[j]\n            j += 1\n        return ans % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        heap_start = []\n        heap_end = []\n        for r in requests:\n            heapq.heappush(heap_start, r[0])\n            heapq.heappush(heap_end, r[1])\n        current = 0\n        p = []\n        for n in range(len(nums)):\n            while heap_start and heap_start[0]<=n:\n                current += 1\n                heapq.heappop(heap_start)\n            while heap_end and heap_end[0]<n:\n                current -= 1\n                heapq.heappop(heap_end)\n            p.append(current)\n        \n        heap = []\n        for i, e in enumerate(p):\n            heapq.heappush(heap, -e)\n        ret = 0\n        heapn = []\n        for n in nums:\n            heapq.heappush(heapn, -n)\n        \n        while heapn:\n            n = heapq.heappop(heapn)\n            ret +=  n*heapq.heappop(heap)\n        return ret % (10**9+7)\n            \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        f=[0 for i in range(len(nums)+1)]\n        for i,j in requests:\n            f[i]+=1\n            f[j+1]-=1\n        pf=[f[0]]\n        for i in range(1,len(f)):\n            pf.append(pf[i-1]+f[i])\n        pf.sort(reverse=True)\n        nums.sort(reverse=True)\n        s=0\n        for i in range(len(nums)):\n            s+=pf[i]*nums[i]\n        return(s%(10**9+7))\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        r = 10**5+1\n        f = [0]*r\n        for s, e in requests:\n            f[s] += 1\n            f[e+1] -= 1\n        freq = {}\n        curr = 0\n        for i in range(r):\n            curr += f[i]\n            if curr != 0:\n                freq[curr] = freq.get(curr, 0) + 1\n        sol = 0\n        nums.sort()\n        for k, v in sorted([(k, v) for k, v in freq.items()], reverse=True):\n            for _ in range(v):\n                sol += k*nums.pop()\n        return sol % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        import numpy\n        weights=numpy.array([0]*len(nums))\n        nums=numpy.array(nums)\n        for l,r in requests: weights[l:r+1]+=1\n        nums.sort() \n        weights.sort()\n        return sum(nums*weights) % (10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        m = len(requests)\n        d = [0] * len(nums)\n        R = sorted(requests, key = lambda x:(x[0],-x[1]))\n        q = []\n        p = -1\n        j = 0\n        for i in range(n):\n            while q and q[0] < i:\n                heapq.heappop(q)\n            while j < m and R[j][0] <= i:\n                heapq.heappush(q, R[j][1])\n                j += 1\n            d[i] = len(q)\n        \n        # print(d)\n        \n        d.sort(reverse=1)\n        nums.sort(reverse=1)\n        ret = 0\n        j = 0\n        for i in d:\n            ret += i * nums[j]\n            j += 1\n        return ret % (10 ** 9 + 7)", "class BinaryIndexedTree:\n    ''' index range from 0 to n-1'''\n    def __init__(self, n):\n        n += 1\n        self.data = [0] * (n)\n        self.n = n\n    def add(self, index, value):\n        index += 1\n        while(index<self.n):\n            self.data[index] += value\n            index += index & -index\n    def prefix(self, index):\n        index += 1\n        res = 0\n        while(index):\n            res += self.data[index]\n            index ^= index & -index\n        return res\n\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], query: List[List[int]]) -> int:\n        MOD = 10 ** 9 + 7\n        n = len(nums)\n        BIT = BinaryIndexedTree(n+1)\n        for l,r in query:\n            BIT.add(l, 1)\n            BIT.add(r+1, -1)\n        count_index = []\n        for i in range(n): \n            # this is O(n log n), can be optimized to O(n) by modifying BIT.data\n            count_index.append((BIT.prefix(i), i))\n        count_index.sort()\n        nums.sort()\n        ans = 0\n        for (ct, _), v in zip(count_index, nums):\n            ans += ct * v\n            ans %= MOD\n        return ans\n", "class Solution:\n    def maxSumRangeQuery(self, A: List[int], E: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        cts = collections.Counter()\n        for a,b in E:\n            cts[a] += 1\n            cts[b+1] -= 1\n        N = len(A)\n        for i in range(N):\n            cts[i] += cts[i-1]\n        freqMap = [(i, cts[i]) for i in range(N)]\n        freqMap.sort(key = lambda a: a[1])\n        A.sort()\n        res = [0]*N\n        for i in range(N):\n            res[freqMap[i][0]] = A[i]\n        psum = [0]\n        for a in res:\n            psum.append(psum[-1] + a)\n        total = 0\n        for a,b in E:\n            total = ( total + psum[b+1] - psum[a]) % MOD\n        return total", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        nums = sorted(nums)\n        mod = 10**9 + 7\n        arry = [0]*(n+1)\n        for x,y in requests:\n            arry[x]+=1\n            arry[y+1]-=1\n        for i in range(1,n+1):\n            arry[i]+=arry[i-1]\n        q = []\n        #print(arry)\n        new_arry = [0]*n\n        for idx,a in enumerate(arry):\n            if a !=0:\n                heapq.heappush(q,(-a,idx))\n        while q:\n            v,idx = heapq.heappop(q)\n            if v==0:break\n            new_arry[idx] = nums.pop()\n        ans = 0\n        for v,times in zip(new_arry,arry):\n            ans+= v*times\n        return ans%mod\n            \n        \n            \n            \n                \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        m = len(requests)\n        pre = [0 for i in range(n+1)]\n        for (l,r) in requests:\n            pre[l] += 1\n            pre[r+1] -= 1\n        cur = 0\n        a = [0 for i in range(n)]\n        for i in range(n):\n            cur += pre[i]\n            a[i] = cur\n        # print(a)\n        # print(nums)\n        a.sort()\n        nums.sort()\n        ans = 0\n        for i in range(n):\n            ans += nums[i] * a[i]\n            # print(nums[i], a[i])\n        return int(ans % (1e9+7))\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        from queue import PriorityQueue\n        from collections import defaultdict\n        q = PriorityQueue()\n        \n        sorted_nums = sorted(nums)\n        \n        dig_dict = defaultdict(int)\n        for r in requests:\n            dig_dict[r[0]] += 1\n            dig_dict[r[1]+1] -= 1\n                \n        for i in range(1, len(nums) + 1):\n            dig_dict[i] += dig_dict[i-1]\n            \n        \n        for k, v in list(dig_dict.items()):\n            q.put((-v, k))\n        \n        final_pos = {}\n        pointer = len(nums) - 1\n        res = 0\n        while q.qsize() > 0:\n            # final_post[q.get()[1]] = sorted_nums[pointer]\n            res += q.get()[0] * -1 * sorted_nums[pointer]\n            pointer -= 1\n        \n        return res % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n, MOD, ans = len(nums), 10**9+7, 0\n        count = [0]*(n+1)\n        for s, e in requests:\n            count[s]+=1\n            count[e+1]-=1\n        for i in range(1, n):\n            count[i]+=count[i-1]\n        have = sorted([c for c in count[:-1] if c], reverse=True)\n        nums.sort(reverse=True)\n        for a, b in zip(have, nums):\n            ans+=(a*b)%MOD\n            ans%=MOD\n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        arr = []\n        for a, b in requests:\n            arr.append([a, -1])\n            arr.append([b, 1])\n        cnt = 0\n        pre = 0\n        arr = sorted(arr)\n        \n        counter = Counter()\n        for e, fg in arr:\n            #print(cnt, e-pre)\n            if fg == -1:\n                counter[cnt] += e-pre\n                pre = e\n                cnt += 1\n            else:\n                counter[cnt] += e+1-pre\n                pre = e+1\n                cnt -= 1\n\n        nums = [-e for e in nums] \n        heapq.heapify(nums)\n        \n        ans = 0\n        for k in sorted(counter.keys())[::-1]:\n            cnt = counter[k]\n            while cnt!=0:\n                cnt -= 1\n                x = -heapq.heappop(nums)\n                ans += x*k\n                ans %= 10**9+7\n        return ans\n        \n                \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        count = [0]*len(nums)\n        for request in requests:\n            count[request[0]] += 1\n            if request[1] < len(nums)-1:\n                count[request[1]+1] -= 1 \n        for i in range(1, len(count)):\n            count[i] += count[i-1]\n        count.sort(reverse = True)\n        nums.sort(reverse = True)\n        res = 0\n        for i in range(len(nums)):\n            res += nums[i]*count[i]\n        return res%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        events = [0]*(10**5+1)\n        for start, end in requests:\n            events[start] += 1\n            events[end+1] -= 1\n        for i in range(1, len(events)):\n            events[i] += events[i-1]\n        events.sort()\n        nums.sort()\n        modulo = 10**9+7\n        answer = 0\n        while nums and events:\n            answer = (answer+nums.pop()*events.pop())%modulo\n        return answer", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        # n = len(nums), m = len(requests)\n        # count all indices in requests - ind_count[ind] = count - time: O(m*n), space: O(n)\n        # start_count = dict()\n        # end_count = dict()\n        # for s, e in requests:\n        #     start_count[s] += 1\n        #     end_count[e+1] += 1\n        # ind_count = dict()\n        # count = 0\n        # for ind in range(n):\n        #     count = count + start_count.get(ind, 0) - end_count.get(ind, 0)\n        #     if count > 0:\n        #         ind_count[ind] = count\n        \n        # sort the indices by counts in descending order - O(n*log(n))\n        # inds = sorted(ind_count.keys(), lambda k: ind_count[k], reverse=True)\n        # sort nums in descending order -> nums - O(n*log(n))\n        # out = 0\n        # for i, ind in enumerate(inds):\n        #   out += ind_count[ind]*nums[i]\n        # O(n)\n        \n        m, n = len(requests), len(nums)\n        ind_count = dict()\n        #for request in requests:\n        #    for i in range(request[0], request[1]+1):\n        #        ind_count[i] = ind_count.get(i, 0) + 1\n        start_count = dict()\n        end_count = dict()\n        for s, e in requests:\n            start_count[s] = start_count.get(s, 0) + 1\n            end_count[e+1] = end_count.get(e+1, 0) + 1\n        count = 0\n        for ind in range(n):\n            count = count + start_count.get(ind, 0) - end_count.get(ind, 0)\n            if count > 0:\n                ind_count[ind] = count\n        \n        inds = sorted(list(ind_count.keys()), key=lambda k: ind_count[k], reverse=True)\n        nums = sorted(nums, reverse=True)\n        out = 0\n        for i, ind in enumerate(inds):\n            out += ind_count[ind]*nums[i]\n        return out % (10**9+7)\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        counts = collections.Counter()\n        A = []\n        for s, e in requests:\n            A.append((s, -1))\n            A.append((e, 1))\n        A.sort()\n        freq, h, last = [0] * n, 0, -1\n        for index, direction in A:\n            if last >= 0:\n                for i in range(last + 1, index):\n                    freq[i] = h\n            last = index\n            if direction == -1:\n                h += 1\n                freq[index] = max(freq[index], h)\n            else:\n                freq[index] = max(freq[index], h)\n                h -= 1\n                \n        freq.sort(reverse = True)\n        nums.sort(reverse = True)\n        idx = res = 0\n        for v in freq:\n            res += nums[idx] * v\n            idx += 1\n        return res % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10 ** 9 + 7\n        weights = defaultdict(int)\n        requests.sort()\n        prev, ends = requests[0][0], [requests[0][1]]\n        for l, r in requests[1:]:\n            while ends and ends[0] < l:\n                weight = len(ends)\n                end = heappop(ends)\n                weights[weight] += (end - prev) + 1\n                prev = end + 1\n                \n            if not ends:\n                prev = l\n                ends = [r]\n            else:\n                weight = len(ends)\n                weights[weight] += (l - prev)\n                prev = l\n                heappush(ends, r)\n                \n        while ends:\n            weight = len(ends)\n            end = heappop(ends)\n            weights[weight] += (end - prev) + 1\n            prev = end + 1  \n        \n        total = 0\n        nums.sort(reverse=True)\n        l = 0\n        for weight in sorted(list(weights.keys()), reverse=True):\n            length = weights[weight]\n            total += (sum(nums[l: l + length]) * weight) % MOD\n            l = l + length\n        return total % MOD\n            \n                \n", "import math\nimport bisect\nfrom typing import List\nfrom collections import defaultdict\n\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n\n        r_arr = [0] * len(nums)\n        MOD = 10 ** 9 + 7\n        for r in requests:\n            r_arr[r[0]] += 1\n            if r[1] < len(r_arr) - 1:\n                r_arr[r[1] + 1] -= 1\n\n        idxes = defaultdict(lambda: [])\n        # curr = 0\n        idxes[r_arr[0]].append(0)\n        for r in range(1, len(r_arr)):\n            # if r_arr[r] > 0:\n            r_arr[r] += r_arr[r - 1]\n            idxes[r_arr[r]].append(r)\n\n        ks = list(idxes.keys())\n        # print(ks)\n        ks.sort(reverse=True)\n\n        res_arr = [0] * len(nums)\n        nums.sort(reverse=True)\n        # print(nums)\n        # print(r_arr)\n        for k in ks:\n            for ele in idxes[k]:\n                res_arr[ele] = nums.pop(0)\n\n        res = 0\n        for i in range(len(res_arr)):\n            res += (res_arr[i] * r_arr[i]) % MOD\n        return res % MOD\n        # return res\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        reqBounds = []\n        for i in range(0, len(requests)):\n            reqBounds.append((requests[i][0], 1))\n            reqBounds.append((requests[i][1] + 1, -1))\n        reqBounds = sorted(reqBounds, key=lambda x: (x[0], -x[1]))\n        weight, curW, prev = [], 0, 0\n        for i in range(0, len(reqBounds)):\n            if reqBounds[i][1] == 1:\n                weight.append((curW, reqBounds[i][0] - prev))\n                curW += 1\n                prev = reqBounds[i][0]\n            else:\n                weight.append((curW, reqBounds[i][0] - prev))\n                curW -= 1\n                prev = reqBounds[i][0]\n        weight = sorted(weight, key=lambda x: -x[0])\n        nums = sorted(nums, key=lambda x: -x)\n        k, ans = 0, 0\n        for i in range(0, len(weight)):\n            for j in range(0, weight[i][1]):\n                ans += weight[i][0] * nums[k]\n                k += 1\n        return ans % (10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        freqs = [0] * (len(nums) + 1)\n        for s, e in requests:\n            freqs[s] += 1\n            freqs[e + 1] -= 1\n        freqs.pop()\n        f = 0\n        for i, (x, n) in enumerate(zip(freqs, nums)):\n            f += x\n            freqs[i] = f\n        nums.sort()\n        freqs.sort()\n        result = 0\n        for n, f in zip(nums, freqs):\n            result += f * n\n        return result % 1000000007\n", "from functools import cmp_to_key\ndef cmp(a,b):\n    x1,y1 = a\n    x2,y2 = b\n    if(x1<x2):\n        return -1\n    elif(x1>x2):\n        return -1\n    else:\n        if(y1=='S'):\n            return 1\n        else:\n            return -1\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        N = len(nums)\n        M = len(requests)\n        l = [0 for i in range(N)]\n        l1 = []\n        for x,y in requests:\n            l1.append((x,'S'))\n            l1.append((y,'E'))\n        l1.sort()\n        i = 0\n        j = 0\n        ct = 0\n        while(i<N):\n            if(j>=2*M):\n                l[i] = ct\n                i += 1\n            elif(i<l1[j][0]):\n                l[i] = ct\n                i += 1\n            elif(i==l1[j][0]):\n                ct1 = 0\n                while(j<2*M and l1[j][0]==i):\n                    if(l1[j][1]=='S'):\n                        ct += 1\n                    else:\n                        ct1 += 1\n                    j += 1\n                l[i] = ct\n                ct -= ct1\n                i += 1\n            else:\n                j += 1\n        \n        '''for x,y in requests:\n            for i in range(x,y+1):\n                l[i] += 1'''\n        \n        l.sort(reverse=True)\n        nums.sort(reverse=True)\n        s = 0\n        for i in range(N):\n            s += l[i]*nums[i]\n        return s%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        stream = []\n        for start, end in requests:\n            stream.append((start, 0))\n            stream.append((end, 1))\n        stream.sort()\n        \n        multiples = []\n        cur_count = 0\n        cur_event = 0\n        for i in range(len(nums)):\n            while cur_event < len(stream) and i == stream[cur_event][0] and stream[cur_event][1] == 0:\n                cur_count += 1\n                cur_event += 1\n            multiples.append(cur_count)\n            while cur_event < len(stream) and i == stream[cur_event][0] and stream[cur_event][1] == 1:\n                cur_count -= 1\n                cur_event += 1\n        \n        multiples.sort(reverse=True)\n        nums.sort(reverse=True)\n        \n        return sum(num * multiple for num, multiple in zip(nums, multiples)) % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mex = 10**5\n        mex+=5\n        ans = [0 for i in range(mex)]\n        for i in requests:\n            x,y = i\n            ans[x]+=1\n            ans[y+1]-=1\n        for i in range(1,mex):\n            ans[i] = ans[i]+ans[i-1]\n        nums.sort(reverse=True)\n        freq = []\n        for i in ans:\n            if i!=0:\n                freq.append(i)\n        freq.sort(reverse=True)\n        mod = 10**9\n        mod+=7\n        cnt = 0\n        for i in range(min(len(freq),len(nums))):\n            cnt = (cnt+((freq[i]*nums[i])%mod))%mod\n        return cnt", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        total = []\n        d = dict()\n        for s,e in requests:\n            d[e] = 1 if e not in d else d[e]+1\n            if s:\n                d[s-1] = -1 if s-1 not in d else d[s-1]-1\n        ld = sorted(d.items())\n        dtotal = []\n        for k,v in ld[::-1]:\n            if not dtotal:\n                dtotal.append(v)\n            else:\n                dtotal.insert(0,dtotal[0]+v)\n        cnt = [0]*len(nums)\n        j = 0\n        for i in range(len(ld)):\n            while j <= ld[i][0]:\n                cnt[j] = dtotal[i]\n                j += 1\n        cnt.sort()\n        nums.sort()\n        ans = 0\n        for i in range(len(cnt)-1,-1,-1):\n            if cnt[i] == 0:\n                break\n            ans += cnt[i]*nums[i]\n        return ans%(10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        if nums==[] or requests==[]:\n            return 0\n        l=len(nums)\n        freqs = [0]*(l+1)\n        for request in requests:\n            start, end = request\n            freqs[start]+=1\n            freqs[end+1]-=1\n        # print(freqs)\n        for i in range(1,l+1):\n            freqs[i]+=freqs[i-1]\n        nums = sorted(nums)\n        freqs = sorted(freqs[:-1])\n        # print(freqs)\n        # print(nums)\n        ans = 0\n        for i in range(l):\n            if freqs[i]==0:\n                continue\n            ans +=(freqs[i]*nums[i])\n        return ans%((10**9)+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        cnt = [0] * n\n        for l, r in requests:\n            cnt[l] += 1\n            if r + 1 < n:\n                cnt[r + 1] -= 1\n        \n        partial_sum = 0\n        for i in range(n):\n            cnt[i] += partial_sum\n            partial_sum = cnt[i]\n        \n        nums.sort()\n        cnt.sort()\n        \n        ans = 0\n        for i in range(n):\n            ans = (ans + nums[i] * cnt[i]) % int(1e9 + 7)\n        return ans\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        freq=[0]*len(nums)\n        for a,b in requests:\n            freq[a]+=1\n            if b+1<len(nums): freq[b+1]-=1\n        for i in range(1,len(nums)):\n            freq[i]+=freq[i-1]\n            \n        freq.sort()\n        nums.sort()\n        ans=0\n        for i in range(len(nums)):\n            ans=(ans+freq[i]*nums[i])%((10**9)+7)\n        return ans\n", "MODULO = 10**9 + 7\n\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        events = [0] * len(nums)\n        for s, e in requests:\n            events[s] += 1\n            if e + 1 < len(nums):\n                events[e + 1] -= 1\n\n        for i in range(1, len(events)):\n            if events[i] == 0:\n                events[i] = events[i-1]\n            else:\n                events[i] = events[i-1] + events[i]\n\n        print(events)\n\n        events.sort()\n        nums.sort()\n\n        summa = 0\n        for v, n in zip(events, nums):\n            summa = (summa + v * n) % MODULO\n        return summa\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        times_requested = [0 for i in range(len(nums))]\n        \n        for request in requests:\n            start, end = request[0], request[1]\n            times_requested[end] += 1\n            if start - 1 >= 0:\n                times_requested[start - 1] -= 1\n        \n        curr_sum = 0\n        for i in range(len(times_requested) - 1, -1, -1):\n            curr_sum += times_requested[i]\n            times_requested[i] = curr_sum\n        \n        times_requested.sort()\n        nums.sort()\n        ans = 0\n        for i in range(len(nums) - 1, -1, -1):\n            ans += times_requested[i] * nums[i]\n            ans = ans % (10 ** 9 + 7)\n        return ans\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        A = nums\n        count = [0 for _ in range(n+1)]\n        for r in requests:\n            start = r[0]\n            end = r[1]\n            count[start] += 1\n            count[end+1] -= 1\n        \n        for i in range(1, n+1):\n            count[i] += count[i-1]\n        # print(count)\n        \n        count = sorted(count, reverse=True)\n        nums = sorted(nums, reverse=True)\n        res = 0\n        for i in range(len(count)):\n            if count[i] == 0:\n                break\n            res += nums[i] * count[i]\n        return res % (10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort()\n        N = len(nums)\n        bucket = [0] * N\n        for a, b in requests:\n            if a < N:\n                bucket[a] += 1\n            if b < N - 1:\n                bucket[b+1] -= 1\n        \n        for i in range(1, N):\n            bucket[i] = bucket[i-1] + bucket[i]\n        bucket.sort()\n        res = 0\n        while bucket and bucket[-1] != 0 and nums[-1] != 0:\n            res = (res + bucket[-1] * nums[-1]) % (10**9 + 7)\n            bucket.pop()\n            nums.pop()\n        return res", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0] * (n+1)\n        \n        for r in requests:\n            start, end = r\n            count[start] += 1\n            count[end+1] -= 1\n        \n        for i in range(1, n):\n            count[i] = count[i-1] + count[i]\n        \n        nums.sort(reverse=True)\n        count.sort(reverse=True)\n        res = 0\n        for num, c in zip(nums, count):\n            if c == 0:\n                break\n            else:\n                res += num * c\n        return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort()\n        N = len(nums)\n        bucket = [0] * N\n        for a, b in requests:\n            if a < N:\n                bucket[a] += 1\n            if b < N - 1:\n                bucket[b+1] -= 1\n        \n        for i in range(1, N):\n            bucket[i] = bucket[i-1] + bucket[i]\n        bucket.sort()\n        res = 0\n        while bucket and bucket[-1] != 0:\n            res = (res + bucket[-1] * nums[-1]) % (10**9 + 7)\n            bucket.pop()\n            nums.pop()\n        return res", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        diff = [0 for i in range(len(nums)+1)]\n        \n        for r in requests:\n            diff[r[0]] += 1\n            diff[r[1]+1] -= 1\n        for i in range(1, len(diff)):\n            diff[i] = diff[i-1] + diff[i]\n        print(diff)\n        diff.sort(reverse = True)\n        nums.sort(reverse = True)\n        answer = 0\n        \n        i = 0\n        while diff[i] != 0:\n            answer += diff[i]*nums[i]\n            answer = answer % (1e9 + 7)\n            i += 1\n        return int(answer)\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums, requests) -> int:\n        chafen=[0]*(len(nums)+1)\n        for req in requests:\n            chafen[req[0]]+=1\n            chafen[req[1]+1]-=1\n        chafen=chafen[:-1]\n        sum_count=[]\n        lastsum=0\n        for idx,cha in enumerate(chafen):\n            lastsum+=cha\n            sum_count.append(lastsum)\n        sum_count=sorted(sum_count)\n        nums=sorted(nums)\n        res=0\n        for idx in range(len(nums)):\n            res+=sum_count[idx]*nums[idx]\n            res%=1e9+7\n        return int(res)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        start_end_count = [[0,0] for _ in nums]\n        for start, end in requests:\n            start_end_count[start][0] += 1\n            start_end_count[end][1] += 1\n        counts = [0 for _ in nums]\n        count = 0\n        for i, (sc, ec) in enumerate(start_end_count):\n            count += sc\n            counts[i] = count\n            count -= ec\n        return sum([a*b % 1000000007 for a, b in zip(sorted(counts), sorted(nums))]) % 1000000007 \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        if N == 0:\n            return 0\n        index_freq = [0 for i in range(N+1)]\n        M = len(requests)\n        for i in range(M):\n            end = requests[i][1]\n            start = requests[i][0]\n            index_freq[start] += 1\n            index_freq[end+1] -= 1\n        total_freq = [0 for i in range(N)]\n        total_freq[0] = index_freq[0]\n        for i in range(1, N):\n            total_freq[i] = index_freq[i] + total_freq[i-1]\n        total_freq.sort(reverse = True)\n        nums.sort(reverse = True)\n        ret = 0\n        for i in range(N):\n            ret += nums[i] * total_freq[i]\n        return ret % 1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        vals = []\n        nums.sort()\n        for i in range(len(nums)):\n            vals.append(0)\n        for request in requests:\n            vals[request[0]] += 1\n            if request[1] + 1 < len(nums):\n                vals[request[1]+1] -= 1\n        count = 0\n        for i in range(len(vals)):\n            vals[i] = vals[i]+count\n            count = vals[i]\n        vals.sort()\n        index = len(nums)-1\n        total = 0\n        while vals[index] != 0 and index >= 0:\n            total += vals[index]*nums[index]\n            index -= 1\n        return total%(10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9 + 7\n        n = len(nums)\n        ans = 0\n        \n        freq = [0] * (n+1)\n        for (a,b) in requests:\n            freq[a] += 1\n            freq[b + 1] -= 1\n        for i in range(1,len(freq)):\n            freq[i] += freq[i-1]\n        freq.sort(reverse = True)\n        nums.sort(reverse = True)\n        return sum([freq[i]*nums[i] for i in range(n)])%MOD\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        diff = [0 for i in range(n+1)]\n        for req in requests:\n            diff[req[0]] += 1\n            diff[req[1] + 1] -= 1\n        for i in range(1, n+1): diff[i] += diff[i-1]\n        diff.pop(-1)\n        sort_idx = [i for i in range(n)]\n        sort_idx = sorted(sort_idx, reverse = True, key = lambda x : diff[x])\n        nums = sorted(nums, reverse = True)\n        temp = [-1 for i in range(n)]\n        for i in range(n): temp[sort_idx[i]] = nums[i]\n        nums = temp[:]\n        temp[0] = nums[0]\n        ret = 0\n        for i in range(1, n): temp[i] = temp[i-1] + nums[i]\n        for req in requests:\n            if (not req[0]): ret += temp[req[1]]\n            else: ret += temp[req[1]] - temp[req[0] - 1]\n            ret %= 1000000007\n        return ret", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        freqs = [0] * (len(nums) + 1)\n        for s, e in requests:\n            freqs[s] += 1\n            freqs[e + 1] -= 1\n        freqs.pop()\n        nzFreqs = []\n        f = 0\n        for i, (x, n) in enumerate(zip(freqs, nums)):\n            f += x\n            if f > 0:\n                nzFreqs.append(f)\n            nums[i] = -n\n        heapq.heapify(nums)\n        nzFreqs.sort(reverse=True)\n        result = 0\n        for f in nzFreqs:\n            result += f * heapq.heappop(nums)\n        return (-result) % 1000000007\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \\\"\\\"\\\"\n \n        \\\"\\\"\\\"\n        import collections\n        request_idx_mapping = collections.defaultdict(int)\n        \n        \n        for open_idx, close_idx in requests:\n            request_idx_mapping[open_idx] += 1\n            request_idx_mapping[close_idx + 1] -= 1\n        request_freq = [0 for _ in range(len(nums))]\n        idxes = [i for i in range(len(nums))]\n        current_requests = 0\n        for idx in range(len(nums)):\n            current_requests += request_idx_mapping[idx]\n            \n            request_freq[idx] = current_requests\n        idxes.sort(key=lambda idx: request_freq[idx], reverse=True)\n        nums.sort()\n        \n        result = 0\n        \n        for idx in idxes:\n            freq = request_freq[idx]\n            num = nums.pop()\n            result += freq*num\n        MOD = 10 ** 9 + 7\n        return result % MOD\n            ", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        '''\n        Discuss Solution thats faster at detecting\n        the number of requests that overlap an index.\n        \n        Key Idea have array t, loop\n        through requests [[start, end] ...]\n        \n        Make t[start] += 1 to indicate\n        every index after start is counted once\n        for this request overlap\n        Make t[end + 1] -= 1 to indicate\n        every index after end + 1 is counted one less\n        for this request overlap\n        \n        The prefix sum of array t tells us\n        the number of requests that overlap\n        an index\n        \n        requests\n        [[0,2],[1,3],[1,1]]\n        \n          -\n          - - -\n        - - -\n        0 1 2 3 4 5\n        1 2 3 4 5 9\n        \n        t\n        0  1  2  3  4  5  6\n        1  2 -1 -1 -1\n        \n        t_prefix\n        0  1  2  3  4  5  6\n        1  3  2  1  0  0  0\n        \n        t.pop to remove index 6\n        Sort both nums and t and\n        use zip to line them up\n        This matches most frequently\n        overlapped index with biggest\n        num.\n        \n        nums\n        1 2 3 4 5 9\n        t\n        0 0 1 1 2 3\n        \n        Multiply because index i gets overlapped\n        t[i] times so the nums value of mapping\n        also gets mulitplied that number of times\n        for the sum\n        \n        nums[i] * t[i]\n        0 0 3 4 10 27\n        \n        sum of final = 44\n        '''\n        t = [0] * (len(nums) + 1)\n        \n        for start, end in requests:\n            t[start] += 1\n            t[end + 1] -= 1\n            \n        for i in range(1, len(nums)):\n            t[i] += t[i - 1]\n        \n        nums.sort()\n        t.pop() # Makes it so t matches length with nums\n        t.sort()\n\n        return sum(a*b for a, b in zip(nums, t)) % (10**9 + 7)\n            \n        \n            \n", "import numpy as np\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n      freq = [0]*(len(nums)+1)\n      for req in requests:\n        freq[req[0]] += 1\n        freq[req[1]+1] -= 1\n      for i in range(1, len(freq)-1):\n        freq[i] = freq[i] + freq[i-1]\n      freq.sort(reverse = True)\n      nums.sort(reverse = True)\n      return sum([x*y for x,y in zip(freq[:-1], nums)]) % (10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        len_nums = len(nums)\n        frequencies = [0] * (len_nums + 1)\n        for start, end in requests:\n            frequencies[start] += 1\n            frequencies[end + 1] -= 1\n        for k in range(1, len_nums):\n            frequencies[k] += frequencies[k - 1]\n        frequencies.sort(reverse=True)\n        nums.sort(reverse=True)\n        max_sum = 0\n        for k in range(len_nums):\n            max_sum += nums[k] * frequencies[k]\n        return max_sum % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0] * (n + 1)\n        for i, j in requests:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(nums)):\n            res += v * c\n        return res % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = 10**9+7\n        starts = list(sorted([s for s, _ in requests]))\n        ends = list(sorted([e for _, e in requests]))\n        \n        r = 0\n        \n        counts = []\n        cur = 0\n        si, ei = 0, 0\n        for i in range(len(nums)):\n            while si < len(starts) and starts[si] <= i:\n                cur += 1\n                si += 1\n            while ei < len(ends) and ends[ei] < i:\n                cur -= 1\n                ei += 1\n            counts.append(cur)\n        \n        sc = list(sorted(counts))\n        sn = list(sorted(nums))\n        \n        # print(sc)\n        # print(sn)\n        \n        for i in range(len(sc)):\n            r += sc[i] * sn[i]        \n        \n        return r % MOD\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        l = [0] * (len(nums) + 1)\n        for a, b in requests:\n            l[a] += 1\n            l[b + 1] -= 1\n        return sum(m * a for m, a in zip(sorted(accumulate(l[:-1])), sorted(nums))) % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        M = 10**9+7\n        \n        n = len(nums)\n        \n        ## count: records the frequency that the range has been requested\n        ## see reference: https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/\n        count = [0] * (n+1)\n        for req in requests:\n            count[req[0]] += 1\n            count[req[1]+1] -= 1\n            \n        ## sort count array by (frequencies, position_index)\n        for i in range(1, n+1):\n            count[i] += count[i-1]\n        counts_ls = [(count[i], i) for i in range(n+1)]\n        counts_ls.sort(key = lambda x: (-x[0], x[1]))\n        \n        ## the greatest number should have the greatest frequency\n        ## so that the sum is maximized\n        nums.sort(key = lambda x: -x)\n        res = 0\n        for i in range(n):\n            res += nums[i] * counts_ls[i][0]\n        return res % M", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        highest = sorted(nums, reverse=True)\n        pointers = [[0,0] for _ in range(len(nums))]\n        for req in requests:\n            pointers[req[0]][0] += 1\n            pointers[req[1]][1] += 1\n        print(pointers)\n        lefts = 0\n        rights = 0\n        freq = []\n        for pointer in pointers:\n            lefts += pointer[0]\n            freq.append(lefts - rights)\n            rights += pointer[1]\n        ans = 0\n        freq.sort(reverse=True)\n        for i in range(len(freq)):\n            \n            ans += freq[i]*highest[i]\n            \n        mod = 10**9 + 7\n        return ans % mod", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        M = 10**9+7\n        \n        n = len(nums)\n        count = [0] * (n+1)\n        for req in requests:\n            count[req[0]] += 1\n            count[req[1]+1] -= 1\n            \n        # print(count)\n        for i in range(1, n+1):\n            count[i] += count[i-1]\n        # print(count)\n        counts_ls = [(count[i], i) for i in range(n+1)]\n        counts_ls.sort(key = lambda x: (-x[0], x[1]))\n        # print(counts_ls)\n        nums.sort(key = lambda x: -x)\n        # print(nums)\n        \n        res = 0\n        for i in range(n):\n            res += nums[i] * counts_ls[i][0]\n        return res % M", "class Solution:\n    def maxSumRangeQuery(self, A, req):\n            n = len(A)\n            count = [0] * (n + 1)\n            for i, j in req:\n                count[i] += 1\n                count[j + 1] -= 1\n            for i in range(1, n + 1):\n                count[i] += count[i - 1]\n            res = 0\n            for v, c in zip(sorted(count[:-1]), sorted(A)):\n                res += v * c\n            return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, a: List[int], r: List[List[int]]) -> int:\n        cnt = [0] * (len(a)+1)\n        for s, e in r: \n            cnt[s] += 1; cnt[e+1] -= 1                    \n        cnt = list(accumulate(cnt))                        \n        return sum(x*y for x, y in zip(sorted(cnt[:-1]), sorted(a))) % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        ans = 0\n        MOD = 10**9+7\n        N=len(nums)\n        walk = Counter()\n        \n        for s,e in requests:\n            walk[s]+=1\n            walk[e+1]-=1\n        \n        vals = []\n        amt = 0\n        for val in range(0,N):\n            amt += walk[val]\n            vals.append(amt)\n        \n        nums.sort()\n        vals.sort()\n        ans = 0\n        for v1,v2 in zip(nums, vals):\n            ans += v1*v2\n        \n        return ans % MOD", "\\\"\\\"\\\"\n0 1 2 3 4 5 6\nX X X X X X X\n  + + +\n+ +\n      + + + +\n\nX X X X X X X\n1 2 1 2 1 1 1\n\n\n-1 0 1 2 3 4 5 6\n   X X X X X X X\n   + + + + + + +   \n\ndiff[i] : freq[i] - freq[i-1]\nfreq[i-1] + diff[i] = freq[i]\n\n[1-3] [2-5]\n0  1  2  3  4  5 \n  +1       -1\n     +1        -1 \n\n---------------------\n0  1  1  0  -1  -1  diff \n0  1  2  2   1   0\n\n\\\"\\\"\\\"\n\n\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0] * (n + 1)\n        for i, j in requests:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(nums)):\n            res += v * c\n        return res % (10**9 + 7)\n        \n        \n        \n        \n        \n        \n        \n        \n        ", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mod = 10**9 + 7\n        rank = [0] * (len(nums) + 1)\n        for i, j in requests:\n            rank[i] += 1\n            rank[j + 1] -= 1\n        for i in range(1, len(nums)):\n            rank[i] = rank[i - 1] + rank[i]\n        \n        rank = rank[:-1]\n        nums.sort()\n        rank.sort()\n        total = 0\n        for i, j in zip(nums,rank):\n            total += i * j\n        return total % mod", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums = sorted(nums, reverse=True)\n        n = len(nums)\n        count = [0] * (n+1)\n        for i,j in requests:\n            count[i] +=1\n            count[j+1] -=1\n        for i in range(1, n):\n            count[i] += count[i-1]\n        counts = sorted(count, reverse=True)\n        res = 0\n        for i in range(n):\n            res+=nums[i]*counts[i]\n        return res % (10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:\n        n = len(A)\n        count = [0] * (n+1)\n        \n        for i, j in req:\n            count[i] += 1\n            count[j+1] -= 1\n            \n        for i in range(1, n+1):\n            count [i] += count[i-1]\n        \n        res = 0\n        A.sort()\n        count.pop()\n        count.sort()\n        \n        for v, c in zip(count, A):\n            res += v * c\n            \n        return res % (pow(10, 9) + 7)\n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        \n        # n = len(A)\n        # count = [0] * (n + 1)\n        # for i, j in req:\n        #     count[i] += 1\n        #     count[j + 1] -= 1\n        # for i in range(1, n + 1):\n        #     count[i] += count[i - 1]\n        # res = 0\n        # for v, c in zip(sorted(count[:-1]), sorted(A)):\n        #     res += v * c\n        # return res % (10**9 + 7)\n", "from itertools import accumulate\nfrom operator import mul\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        cums = [0 for i in range(len(nums)+1)]\n        for start,end in requests:\n            cums[start]+=1\n            cums[end+1]-=1\n        return sum( map(mul,sorted(accumulate(cums),reverse=True),sorted(nums,reverse=True) ))%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        MOD = (10**9+7)\n        n = len(nums)\n        ranks = [0]*(n+1)\n        for start,end in requests:\n            ranks[start] += 1\n            ranks[end+1] -= 1\n        for i in range(1,n+1):\n            ranks[i] += ranks[i-1]\n        ranks = ranks[:n]\n        ranks.sort()\n        nums.sort()\n        ans = 0\n        for i in range(len(ranks)):\n            ans += ranks[i]*nums[i]\n        return ans % MOD", "class Solution:\n    def maxSumRangeQuery(self, A: List[int], req: List[List[int]]) -> int:\n        n = len(A)\n        count = [0] * (n + 1)\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(A)):\n            res += v * c\n        return res % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, A, req):\n        n = len(A)\n        count = [0] * (n + 1)\n        for i, j in req:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(A)):\n            res += v * c\n        return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        occurances = [0] * len(nums)\n        for request in requests:\n            occurances[request[0]] += 1\n            if (request[1] + 1 < len(nums)):\n                occurances[request[1] + 1] -= 1\n        for i in range(1, len(nums)):\n            occurances[i] += occurances[i - 1]\n        mod = int(1e9+7)\n        occurances.sort()\n        nums.sort()\n        res = 0\n        for i in range(len(nums)):\n            res = (res + nums[i] * occurances[i]) % mod\n        return res", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        # We want to calculate the frequency for A[i].\n        # Assign the big element A[i] to the position queried more frequently.\n        n = len(nums)\n        count = [0] * (n + 1)\n        \n        for i, j in requests:\n            count[i] += 1\n            count[j + 1] -= 1\n            \n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n            \n        res = 0\n        for v, c in zip(sorted(count[:-1]), sorted(nums)):\n            res += v * c\n            \n        return res % (10**9 + 7)\n    \n    \n", "class Solution:\n    def maxSumRangeQuery(self, nums, requests) -> int:\n        \\\"\\\"\\\"\n        Given an array of integers (nums) and an array of range\n        requests (requests), each request containing the start\n        and end indexes of a range within nums, this program\n        determines the maximum sum over requests for all permutations\n        of nums.\n\n        :param nums: array of integers\n        :type nums: list[int]\n        :param requests: array of range requests, each containing\n                         the start and end indexes of a range of\n                         indexes within nums\n        :type requests: list[list[int]]\n        :return: maximum sum over the range requests (requests)\n        :rtype: int\n        \\\"\\\"\\\"\n\n        \\\"\\\"\\\"\n        Initialize length of nums array (len_nums)\n        \\\"\\\"\\\"\n        len_nums = len(nums)\n\n        \\\"\\\"\\\"\n        Determine the frequency for each index within nums\n        \\\"\\\"\\\"\n        frequencies = [0] * (len_nums + 1)\n        for start, end in requests:\n            frequencies[start] += 1\n            frequencies[end + 1] -= 1\n        for k in range(1, len_nums):\n            frequencies[k] += frequencies[k - 1]\n\n        \\\"\\\"\\\"\n        Determine the maximum range sum (max_sum).\n        \\\"\\\"\\\"\n        frequencies.sort(reverse=True)\n        nums.sort(reverse=True)\n        max_sum = 0\n        for num, frequency in zip(nums, frequencies):\n            max_sum += num * frequency\n        return max_sum % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        temp = [0]*(n+1)\n        \n        for ind,i in enumerate(requests):\n            s = i[0]; e = i[1]\n            temp[s]+=1\n            temp[e+1]-=1\n            \n        for i in range(1,n+1):\n            temp[i] += temp[i-1]\n            \n        temp = sorted(temp,reverse = 1)\n        nums = sorted(nums,reverse = 1)\n    \n        ans = 0\n        for i in range(n):\n            ans += nums[i]*temp[i]\n        \n        return ans%((10**9)+7)", "from collections import Counter, deque\nfrom itertools import chain\n\nimport heapq\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        f = [0] * (len(nums) + 1)\n        for i, j in requests:\n            f[i] += 1\n            f[j+1] -= 1\n        for i in range(1, len(nums) + 1):\n            f[i] += f[i - 1]\n        return sum(x * y for x, y in zip(sorted(f, reverse=True), sorted(nums, reverse=True))) % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        mod = 10**9 + 7\n        n = len(nums)\n        t = [0]*(n + 1)\n        for a, b in requests:\n            t[a] += 1\n            t[b + 1] -= 1\n        for i in range(1, n):\n            t[i] += t[i - 1]\n        \n        nums.sort()\n        t.pop()\n        t.sort()\n\n        return sum(a*b for a, b in zip(nums, t)) % mod", "from collections import Counter, deque\nfrom itertools import chain\n\nimport heapq\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        f = [0] * (len(nums) + 1)\n        for i, j in requests:\n            f[i] += 1\n            f[j+1] -= 1\n        for i in range(1, len(nums) + 1):\n            f[i] += f[i - 1]\n        \n        f.sort(reverse=True)\n        nums.sort(reverse=True)\n        return sum(x * y for x, y in zip(f, nums)) % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, A, qs):\n        A.sort(reverse=1)\n        n=len(A)\n        r=[0]*(n+1)\n        for a,b in qs:\n            r[a]+=1\n            r[b+1]-=1\n        for i in range(1,n):\n            r[i]+=r[i-1]\n        r.pop()\n        r.sort(reverse=1)\n        ans=0\n        for i,k in enumerate(r):\n            ans+=A[i]*k\n        return ans%(10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        index_count = [0]* (len(nums)+1)\n        for request in requests:\n            index_count[request[0]]+= 1\n            index_count[request[1]+1]-= 1\n            \n        for i in range(1, len(index_count)):\n            index_count[i] += index_count[i-1]\n        nums.sort(reverse = True)\n        index_count.sort(reverse=True)\n       \n        res = sum(i* v for i,v in zip(nums, index_count))\n        return res %( 10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0]*(n+1)\n        for i in range(len(requests)):\n            start = requests[i][0]\n            end = requests[i][1]\n            count[start]+=1\n            count[end+1]-=1\n        for i in range(1,n):\n            count[i]+=count[i-1]\n        #print(count)\n        x=count.pop()\n        nums.sort(reverse=True)\n        count.sort(reverse=True)\n        #print(nums)\n        #print(count)\n        ans = 0\n        for i in range(n):\n            ans+=(count[i]*nums[i])%(10**9+7)\n        \n        return ans%(10**9+7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        len_nums = len(nums)\n\n        \\\"\\\"\\\"\n        Determine the frequency for each index within nums\n        \\\"\\\"\\\"\n        frequencies = [0] * (len_nums + 1)\n        for start, end in requests:\n            frequencies[start] += 1\n            frequencies[end + 1] -= 1\n        for k in range(1, len_nums):\n            frequencies[k] += frequencies[k - 1]\n\n        \\\"\\\"\\\"\n        Determine the maximum range sum (max_sum).\n        \\\"\\\"\\\"\n        frequencies.sort(reverse=True)\n        nums.sort(reverse=True)\n        max_sum = 0\n        for num, frequency in zip(nums, frequencies):\n            max_sum += num * frequency\n        return max_sum % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        count = [0] * len(nums)\n        for i, j in requests:\n            count[i] += 1\n            if j + 1 < len(count):\n                count[j+1] -= 1\n        cur = 0\n        for i in range(len(count)):\n            count[i] += cur\n            cur = count[i]\n        return sum(n * c for n, c in zip(sorted(nums, reverse=True), sorted(count, reverse=True))) % (10 ** 9 + 7)\n            \n", "import heapq\n\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        # build heat map\n        # put highest numbers in hottest spots\n        heatMap = [0 for i in range(len(nums)+1)]\n        for req in requests:\n            heatMap[req[0]] += 1\n            heatMap[req[1]+1] -= 1 \n            # for i in range(req[0], req[1]+1):\n            #     heatMap[i] += 1\n        for i in range(1,len(heatMap)):\n            heatMap[i] += heatMap[i-1]\n        heatMap.sort(reverse=True)\n        # heap of non-zero size heatMap\n        nums.sort(reverse=True)\n        numIndex = 0\n        total = 0\n        for count in heatMap:\n            if count == 0:\n                break\n            total += nums[numIndex] * count\n            numIndex += 1\n        return total % (10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        total = 0\n        prefix = [0] * len(nums)\n        for x, y in requests:\n            prefix[x] += 1\n            if y < len(prefix) - 1:\n                prefix[y + 1] -= 1\n        for i in range(len(prefix) - 1):\n            prefix[i+1] += prefix[i]\n        nums.sort(reverse=True)\n        prefix.sort(reverse=True)\n        for i in range(len(nums)):\n            total += (nums[i] * prefix[i])\n        total %= (10 ** 9 + 7)\n        return total\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        pref = [0] * n\n        for req in requests:\n            l, r = req\n            pref[l] += 1\n            if r + 1 < n: pref[r + 1] -= 1\n        \n        for i in range(1, n):\n            pref[i] += pref[i - 1]\n        \n        \n        pref.sort()\n        nums.sort()\n        \n        ans = 0\n        MOD = 10 ** 9 + 7\n        \n        for i in range(n):\n            ans = (ans + nums[i] * pref[i]) % (MOD)\n        \n        return ans\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        # calculate position count\n        # permutation by sorting\n        reqs = [0] * (len(nums) + 1)   # idx, +1/-1\n        for request in requests:\n            reqs[request[0]] += 1\n            reqs[request[1] + 1] -= 1\n        prev = 0\n        reqs.pop()\n        for i in range(len(reqs)):\n            reqs[i] += prev\n            prev = reqs[i]\n        \n        #print(reqs)\n        nums.sort(reverse = True)\n        reqs.sort(reverse = True)\n        \n        ret = 0\n        M = pow(10, 9) + 7\n        for i in range(len(nums)):\n            ret = (ret + nums[i] * reqs[i]) % M\n        \n        return ret\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n, m = len(nums), len(requests)\n        count = [0 for _ in range(n + 1)]\n        for begin, end in requests:  \n            count[begin] += 1\n            count[end + 1] -= 1\n        for i, c in enumerate(count):\n            if i != 0:\n                count[i] += count[i-1]\n        nums.sort(reverse=True)\n        count.sort(reverse=True)\n        total = 0\n        for num, count in zip(nums,count):\n            total += (num * count)\n        return total % (10**9 + 7)\n        \n        \n        \n\\\"\\\"\\\"\n  1 2 3\n0,1\n\n\\\"\\\"\\\"", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        calls = [0] * (len(nums) + 1)\n        for start, end in requests:\n            calls[start] += 1\n            calls[end+1] -= 1 \n        for i in range(1, len(calls)):\n            calls[i] += calls[i-1]\n        calls.sort(reverse=True)\n        nums.sort(reverse=True)\n        return sum([i * j for i, j in zip(calls[:-1], nums)])%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        occurances = [0] * len(nums)\n        for request in requests:\n            occurances[request[0]] += 1\n            if (request[1] + 1 < len(nums)):\n                occurances[request[1] + 1] -= 1\n        for i in range(1, len(nums)):\n            occurances[i] += occurances[i - 1]\n        mod = int(1e9+7)\n        occurances.sort()\n        nums.sort()\n        res = 0\n        for (x, y) in zip(occurances, nums):\n            res = (res + x * y) % mod\n        return res", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N=len(nums)\n        add=(N+1)*[0]\n        ded=(N+1)*[0]\n        M=len(requests)\n        for start,end in requests:\n            add[end+1]+=1\n            ded[start]+=1\n        dp=N*[0]\n        z1=0\n        z2=0\n        for i in range(N):\n            z1+=add[i]\n            z2+=ded[i]\n            dp[i]=z2-z1\n        nums.sort()\n        dp.sort()\n        return sum(nums[i]*dp[i] for i in range(N))%(10**9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        total = 0\n        prefix = [0] * len(nums)\n        \n        for x, y in requests:\n            prefix[x] += 1\n            if y < len(prefix) - 1:\n                prefix[y + 1] -= 1\n                \n        for i in range(len(prefix) - 1):\n            prefix[i+1] += prefix[i]\n        \n        nums.sort(reverse=True)\n        prefix.sort(reverse=True)\n        for i in range(len(nums)):\n            total += (nums[i] * prefix[i])\n        total %= (10 ** 9 + 7)\n        return total\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        res = 0\n        MOD = 10**9 + 7\n        ln = len(nums)\n        c = [0]*(ln+1)\n        for r in requests:\n          c[r[0]] += 1\n          c[r[1]+1] -= 1\n        for i in range(1, ln):\n          c[i] += c[i-1]\n        \n        \n        #c = sorted([(i, v) for i, v in enumerate(c)], key=lambda x: -x[-1])\n        # print (c)\n        nums = sorted(nums, key=lambda x:-x)      # nlogn\n        ctr = collections.defaultdict(lambda : 0)\n        for cv in c:\n          ctr[cv] += 1\n        # print (ctr)\n        \n        j = 0\n        for i in range(len(requests), 0, -1):\n          # print (ctr[i])\n          m = ctr[i]\n          while m:\n            res += (nums[j]*i)%MOD\n            j += 1\n            m -= 1\n            res = res%MOD\n          \n        return res%MOD\n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        arr=[0]*(len(nums)+1)\n        for s,e in requests:\n            arr[s]+=1\n            arr[e+1]-=1\n        for i in range(1,len(arr)):\n            arr[i]+=arr[i-1]\n        arr.pop()\n        arr.sort()\n        res=0\n        for i,v in enumerate(sorted(nums)):\n            res+=v*arr[i]\n            res%=(10**9+7)\n        return res", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n, m = len(nums), len(requests)\n        count = [0 for _ in range(n + 1)]\n        for begin, end in requests:  \n            count[begin] += 1\n            count[end + 1] -= 1\n        for i, c in enumerate(count):\n            if i != 0:\n                count[i] += count[i-1]\n        nums.sort(reverse=True)\n        count.sort(reverse=True)\n        total = 0\n        for num, count in zip(nums,count):\n            if count == 0: break\n            total += (num * count)\n        return total % (10**9 + 7)\n        \n        \n        \n\\\"\\\"\\\"\n  1 2 3\n0,1\n\n\\\"\\\"\\\"", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        q = [] ; ans = 0 ; L_n = len(nums) ; L_r = len(requests)\n        for i in range(L_n):\n            q.append(0)\n        for i in range(L_r) :\n            q[requests[i][0]] += 1\n            now = requests[i][1]+1\n            if now < len(q):\n                q[now] -= 1 \n        for i in range(1,L_n) :\n            q[i] += q[i-1]\n        q.sort(reverse=True) ; nums.sort(reverse=True)\n        for i in range(L_n):\n            if q[i] == 0 : \n                q = q[0:i]\n                break\n        for i in range(len(q)) :\n            ans += q[i] * nums[i]\n            ans = ans %(10**9 + 7 )\n        return ans", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums.sort(reverse=True)\n        ans = 0\n        MOD = 10 ** 9 + 7\n        cnt = [0] * (len(nums) + 1)\n        for r in requests:\n            cnt[r[0]] += 1\n            cnt[r[-1] + 1] -= 1 \n        for i in range(1, len(nums)):\n            cnt[i] += cnt[i - 1]\n        cnt = cnt[:-1]\n        v = sorted(enumerate(cnt), key=operator.itemgetter(1), reverse=True)\n        j = 0\n        for _, k in v:\n            ans += nums[j] * k\n            j += 1\n        return ans % MOD", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        counts = [0] * (len(nums) + 1)\n        for start, end in requests:\n            counts[start] += 1\n            counts[end + 1] -= 1\n        for i in range(1, len(nums)):\n            counts[i] += counts[i - 1]\n        counts.sort(reverse = True)\n        nums.sort(reverse = True)\n        return sum(c * n for c, n in zip(counts, nums)) % (10 ** 9 + 7)\n", "from heapq import heappush,heappop\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0]*(n+1)\n        for request in requests:\n            start,end = request\n            # amazing way to find frequency at each index without looping\n            # from start to end\n            count[start]+=1\n            count[end+1]-=1\n        \n        for i in range(1,n+1):\n            # using prefix sum\n            count[i]+=count[i-1]\n        answer = 0\n        nums.sort()\n        c = count[:-1]\n        c.sort()\n        for a,b in zip(nums,c):\n            answer += a*b\n        \n        mod = (10**9)+7\n        return answer%mod\n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        nums = sorted(nums)\n        n = len(nums)\n        freq = [0] * (n+1)\n        for l, r in requests:\n            freq[l] += 1\n            freq[r+1] -= 1\n        for i in range(1, n):\n            freq[i] += freq[i-1]\n        freq = sorted(freq[:n])\n        return sum(freq[i] * nums[i] for i in range(n)) % 1000000007", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], reqs: List[List[int]]) -> int:\n        MOD = int(1e9)+7\n        n = len(nums)\n        weights = [0 for _ in range(n)]\n        \n        for x,y in reqs:\n            weights[x]+=1\n            if y<n-1:\n                weights[y+1]-=1\n        \n        for i in range(1,n):\n            weights[i] += weights[i-1]\n        \n        print(weights)\n        \n        weights.sort(reverse = True)\n        nums.sort(reverse = True)\n        ans = 0\n        \n        for i in range(n):\n            ans += weights[i]*nums[i]\n            \n        return ans % MOD\n            \n        \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        \n        frequency = [0 for i in range(len(nums))]\n        \n        \n        for u, v in requests:\n            \n            frequency[u] += 1\n            if v + 1 < len(nums): frequency[v + 1] -= 1\n                \n        for i in range(1, len(frequency)):\n            \n            frequency[i] += frequency[i - 1]\n            \n        frequency.sort()\n        nums.sort()\n        \n        Sum = 0\n        while nums:\n            \n            Sum += nums.pop()*frequency.pop()\n            \n        return Sum%(10**9 + 7)\n            \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        count = [0] * (n + 1)\n        for i, j in requests:\n            count[i] += 1\n            count[j + 1] -= 1\n        for i in range(1, n + 1):\n            count[i] += count[i - 1]\n        # print(count)\n        count.sort(reverse = True)\n        res = 0\n        nums.sort()\n        for i in range(n):\n            if count[i] == 0:\n                break\n            res += count[i] * nums.pop()\n        return res % (10 ** 9+7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        #sort the array nums\n        nums.sort(reverse = True)\n        N, M = len(nums), len(requests)\n        freq = [0 for i in range(N+1)]\n        res = 0\n\n        for start, end in requests:\n            freq[start] += 1\n            freq[end + 1] -= 1\n        for i in range(1, N+1):\n            freq[i] += freq[i-1]\n        freq.sort(reverse = True)\n        for i in range(N):         \n            res += freq[i] * nums[i]\n            if freq[i] == 0 or nums[1] == 0:\n                break\n        return res%(10**9 + 7)\n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        n = len(nums)\n        ind = [0] * (n+1)\n        \n        for i,j in requests:\n            ind[i] += 1\n            ind[j+1] -= 1\n        \n        for i in range(1, n):\n            ind[i] += ind[i-1]\n        \n        ind = sorted(list(zip(ind,range(n))))\n        nums = sorted(nums)\n        \n        res = 0\n        while ind:\n            x,y = ind.pop()\n            if x == 0:\n                return res % (10**9 + 7)\n            res += x*nums.pop()\n        \n        return res % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        ''' https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854153/Simple-solution-Python-O(n)\n            Find most requested position and calculate sum request_count * element(order of request_count) .\n        '''\n        mod = 10**9+7\n        n = len(nums)\n        arr = [0] * (n+1) # add extra element for handel n+1 case\n        for i, j in requests:\n            arr[i] += 1\n            arr[j+1] -= 1\n        for i in range(1, n+1):\n            arr[i] += arr[i-1]\n        arr = arr[:n] # remove the extra element\n        nums.sort()\n        arr.sort()\n        ans = 0\n        for i in range(n):\n            ans += nums[i] * arr[i]\n        return ans%mod", "from collections import Counter\nclass Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n                \n        # 1a. Find optimal permutation of nums. O(N^2) / O(requests * len(requests))\n            # Create Counter with number of entries for each number. \n            # Sort # of requests from large to small\n        # c = {i : 0 for i, v in enumerate(nums)}\n        # for r in requests:\n        #     for i in range(r[0], r[1] + 1):\n        #         c[i] += 1\n        # requests_per_num = [c[k] for k in c]\n        # requests_per_num.sort(reverse=True) \n        \n        # 1b. Let's try to do this in O(N) + O(R) time. \n        # Create Counters of start / end values of requests.\n        start = Counter([r[0] for r in requests])\n        end = Counter([r[1] for r in requests])\n\n        # Loop through possible nums.\n        running_sum = 0\n        requests_per_num = []\n        \n        # Use counter to update num requests. \n        for i, n in enumerate(nums):\n            running_sum += start[i]\n            running_sum -= end[i - 1]\n            requests_per_num.append(running_sum)\n        requests_per_num.sort(reverse=True) \n            \n        # 2. Order numbers to match most common requests.\n        nums_copy = [n for n in nums]\n        nums_copy.sort(reverse=True)\n        \n        # Compute sum.\n        max_sum = 0\n        for n, r in zip(nums_copy, requests_per_num):\n            max_sum += n * r\n            \n        # Return max sum mod 10 ** 9 + 7\n        return max_sum % (10 ** 9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        frequency = [0 for i in range(len(nums))]\n        for request in requests:\n            start,end = request\n            frequency[start] += 1\n            if end+1 < len(frequency):\n                frequency[end+1] -= 1\n        \n        indexToFrequency = []\n        for i in range(0,len(frequency)):\n            if i != 0:\n                frequency[i] += frequency[i-1]\n            indexToFrequency.append((frequency[i],i))\n        indexToFrequency.sort(reverse = True)\n        nums.sort(reverse = True)\n        \n        numbers = [0 for _ in range(len(nums))]\n        for i in range(len(indexToFrequency)):\n            _,index = indexToFrequency[i]\n            numbers[index] = nums[i]\n        \n        prefixSum = list(numbers)\n        for i in range(1,len(numbers)):\n            prefixSum[i] += prefixSum[i-1]\n            prefixSum[i] %= (10 ** 9 + 7)\n            \n        result = 0\n        for request in requests:\n            start,end = request\n            if start == 0:\n                result += prefixSum[end]\n            else:\n                result += (prefixSum[end]-prefixSum[start-1])\n            result = result % (10 ** 9 + 7)\n        return result\n        \n        \n        \n        \n        \n        \n            \n", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        indmap = {ind:0 for ind in range(len(nums))}\n        for r in requests:\n            indmap[r[0]] += 1\n            if r[1]+1 < len(nums):\n                indmap[r[1]+1] -=1\n        for i in range(1, len(nums)):\n            indmap[i] += indmap[i-1]\n        \n        indices_sorted_by_occ = sorted(indmap.keys(), key= lambda ind: indmap[ind], reverse=True)\n        sorted_freqs = [indmap[ind] for ind in indices_sorted_by_occ]\n                \n        sorted_nums = sorted(nums, reverse = True)\n        sol = sum(n*f for n, f in zip(sorted_nums, sorted_freqs))\n        \n        return sol % (10**9 + 7)", "class Solution:\n    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:\n        N = len(nums)\n        i_count = [0] * N\n\n        for start, end in requests:\n            i_count[start] += 1\n\n            if end + 1 < N:\n                i_count[end + 1] -= 1\n\n        for i in range(1, N):\n            i_count[i] += i_count[i - 1]\n\n        s = 0\n        m = 1000000007\n        i_count.sort()\n        nums.sort()\n        for i in range(N):\n            s += i_count[i] * nums[i]\n\n        return s % m"]