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: MEDIUM
Tags: Sorting

Data structures

Range queries

Greedy algorithms
Skill types: Sorting

Data structures

Range queries

Greedy algorithms

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

Solutions:
class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		count = [0] * (len(nums) + 1)
		for (start, end) in requests:
			count[start] += 1
			count[end + 1] -= 1
		for i in range(1, len(nums) + 1):
			count[i] += count[i - 1]
		count.pop()
		res = 0
		for (n, times) in zip(sorted(nums), sorted(count)):
			res += n * times
		return res % (10 ** 9 + 7)


class Solution:

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


class Solution:

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


class Solution:

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


from collections import defaultdict

class Solution:

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


class Solution:

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


class Solution:

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


from heapq import *

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		MOD = 10 ** 9 + 7
		nums.sort(reverse=True)
		j = 0
		s = 0
		cnts = []
		n = len(nums)
		count = [0] * (n + 1)
		for (i, j) in requests:
			count[i] += 1
			count[j + 1] -= 1
		for i in range(1, n + 1):
			count[i] += count[i - 1]
		count.sort(reverse=True)
		s = 0
		for i in range(len(nums)):
			if count[i] > 0:
				s += count[i] * nums[i]
			else:
				break
		return s % MOD


class Solution:

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


from collections import Counter

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		a = [0 for i in range(len(nums) + 1)]
		for i in requests:
			a[i[0]] += 1
			a[i[1] + 1] -= 1
		for i in range(1, len(a)):
			a[i] = a[i] + a[i - 1]
		a.pop(-1)
		nums = sorted(nums, reverse=True)
		pair = [[0, number, index] for (index, number) in enumerate(a)]
		pair = sorted(pair, key=lambda word: -word[1])
		for i in range(len(nums)):
			pair[i][0] = nums[i]
		maxSum = 0
		for i in pair:
			maxSum += i[0] * i[1]
		return maxSum % (10 ** 9 + 7)


class Solution:

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


class Solution:

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


from collections import deque

class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		N = len(nums)
		i_count = [0] * N
		for (start, end) in requests:
			i_count[start] += 1
			if end + 1 < N:
				i_count[end + 1] -= 1
		for i in range(1, N):
			i_count[i] += i_count[i - 1]
		s = 0
		m = 1000000007
		i_count.sort()
		nums.sort()
		for i in range(N):
			s += i_count[i] * nums[i]
			if s > m:
				s %= m
		return s


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		heap = []
		dict = defaultdict(int)
		requests.sort()
		count = 0
		start = 0
		for i in requests:
			while heap and heap[0] < i[0]:
				heap_pop = heapq.heappop(heap)
				dict[count] += heap_pop + 1 - start
				start = heap_pop + 1
				count -= 1
			heapq.heappush(heap, i[1])
			dict[count] += i[0] - start
			start = i[0]
			count += 1
		while heap:
			heap_pop = heapq.heappop(heap)
			dict[count] += heap_pop + 1 - start
			start = heap_pop + 1
			count -= 1
		nums.sort(reverse=True)
		index = 0
		res = 0
		sort_key = sorted(list(dict.keys()), reverse=True)
		for key in sort_key:
			res += key * sum(nums[index:index + dict[key]])
			res %= 10 ** 9 + 7
			index += dict[key]
		return res


class Solution:

	def maxSumRangeQuery(self, A, req):
		n = len(A)
		count = [0] * (n + 1)
		for (i, j) in req:
			count[i] += 1
			count[j + 1] -= 1
		count = list(accumulate(count))[:-1]
		count.sort()
		A.sort()
		return sum([count[i] * A[i] for i in range(n)]) % (10 ** 9 + 7)


class Solution:

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


from collections import defaultdict

class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		cnt = [0, 0]
		mod = 10 ** 9 + 7
		requests.sort()
		n = len(nums)
		cnt = [0] * n
		for (s, e) in requests:
			cnt[s] += 1
			if e + 1 < n:
				cnt[e + 1] -= 1
		print(cnt)
		real_cnt = []
		for c in cnt:
			real_cnt += [c + (real_cnt[-1] if real_cnt else 0)]
		cnt = real_cnt
		cnt.sort()
		nums.sort()
		print(cnt, nums)
		res = 0
		for (n, c) in zip(nums, cnt):
			res += n * c
		return res % (10 ** 9 + 7)


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


import heapq

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		mymap = collections.defaultdict(int)
		n = len(nums)
		freqs = [0] * (n + 1)
		for (i, j) in requests:
			freqs[i] += 1
			freqs[j + 1] -= 1
		for i in range(1, n + 1):
			freqs[i] += freqs[i - 1]
		freqs = sorted(freqs[:-1], reverse=True)
		heap = [(-n, n) for n in nums]
		heapq.heapify(heap)
		tot = 0
		for (i, freq) in enumerate(freqs):
			num = heapq.heappop(heap)[1]
			tot += num * freq
			tot %= 10 ** 9 + 7
		return tot % (10 ** 9 + 7)


class Solution:

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


mod = 10 ** 9 + 7

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		n = len(nums)
		arr = [0] * (n + 1)
		for (i, j) in requests:
			arr[i] += 1
			arr[j + 1] -= 1
		for i in range(1, n + 1):
			arr[i] += arr[i - 1]
		arr = arr[:n]
		nums.sort()
		arr.sort()
		ans = 0
		for i in range(n):
			ans += nums[i] * arr[i]
		return ans % mod


from collections import defaultdict

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from collections import Counter

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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

		def _push_down(rt, diff):
			lazy[rt * 2 + 1] += diff
			lazy[rt * 2 + 2] += diff

		def update_range_by_one(rt, lo, hi, i, j):
			if j < lo or i > hi:
				return
			if lazy[rt] != 0:
				tree[rt] += (hi - lo + 1) * lazy[rt]
				if lo != hi:
					_push_down(rt, lazy[rt])
				lazy[rt] = 0
			if lo >= i and hi <= j:
				tree[rt] += hi - lo + 1
				if lo != hi:
					_push_down(rt, 1)
				return
			mid = (lo + hi) // 2
			update_range_by_one(rt * 2 + 1, lo, mid, i, j)
			update_range_by_one(rt * 2 + 2, mid + 1, hi, i, j)
			tree[rt] = tree[2 * rt + 1] + tree[2 * rt + 2]

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		freq = [0] * (len(nums) + 1)
		for l in requests:
			freq[l[0]] += 1
			freq[l[1] + 1] -= 1
		for i in range(1, len(freq)):
			freq[i] += freq[i - 1]
		ans = 0
		for (x, y) in zip(sorted(freq[:-1]), sorted(nums)):
			ans += x * y
		return ans % 1000000007


from collections import Counter

class Solution:

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


class Solution:

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


class Solution:
	import heapq

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		MOD = 10 ** 9 + 7
		n = len(nums)
		events = []
		OPEN = -1
		CLOSE = 1
		for (u, v) in requests:
			events.append([u, OPEN])
			events.append([v, CLOSE])
		events.sort()
		weights = [0] * n
		open_events = 0
		nxt_event = 0
		for i in range(n):
			while nxt_event < len(events) and events[nxt_event][0] <= i:
				if events[nxt_event][1] == OPEN:
					open_events += 1
				else:
					break
				nxt_event += 1
			weights[i] = open_events
			while nxt_event < len(events) and events[nxt_event][0] <= i:
				if events[nxt_event][1] == CLOSE:
					open_events -= 1
				nxt_event += 1
		return sum([w * num for (w, num) in zip(sorted(weights), sorted(nums))]) % MOD


class Solution:

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


class Solution:

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


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

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from collections import defaultdict

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		points = []
		for req in requests:
			points.append([req[0], 0])
			points.append([req[1], 1])
		points.sort(key=lambda e: (e[0], e[1]))
		freqCnt = defaultdict(int)
		pos = None
		cnt = 0
		for p in points:
			if pos != None:
				if p[1] == 0:
					freqCnt[cnt] += p[0] - pos
				else:
					freqCnt[cnt] += p[0] - pos + 1
			if p[1] == 0:
				cnt += 1
			else:
				cnt -= 1
			if cnt == 0:
				pos = None
			elif p[1] == 0:
				pos = p[0]
			else:
				pos = p[0] + 1
		nums.sort(reverse=True)
		result = 0
		i = 0
		for (k, v) in sorted(list(freqCnt.items()), reverse=True):
			result += k * sum(nums[i:i + v])
			i += v
		return result % (10 ** 9 + 7)


class Solution:

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

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


class Solution:

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


class Solution:

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


from typing import List
import collections

class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		N = len(nums)
		i_count = [0] * N
		for (start, end) in requests:
			i_count[start] += 1
			if end + 1 < N:
				i_count[end + 1] -= 1
		for i in range(1, N):
			i_count[i] += i_count[i - 1]
		return sum((a * b for (a, b) in zip(sorted(i_count), sorted(nums)))) % 1000000007


from collections import defaultdict
MOD = int(1000000000.0 + 7)

class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		i_count = Counter()
		first = float('inf')
		last = -first
		for (start, end) in requests:
			i_count[start] += 1
			i_count[end + 1] -= 1
			first = min(first, start)
			last = max(last, end)
		q = []
		s = 0
		for p in range(first, last + 1):
			s += i_count[p]
			q.append(-s)
		heapq.heapify(q)
		ans = 0
		nums.sort()
		while q:
			ans = (ans + nums.pop() * -heapq.heappop(q)) % 1000000007
		return ans


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		requestCount = defaultdict(int)
		begHeap = []
		endHeap = []
		for req in requests:
			heapq.heappush(begHeap, req[0])
			heapq.heappush(endHeap, req[1] + 1)
		poppedCount = 0
		for i in range(len(nums)):
			while begHeap and begHeap[0] <= i:
				heapq.heappop(begHeap)
				poppedCount += 1
			while endHeap and endHeap[0] <= i:
				heapq.heappop(endHeap)
				poppedCount -= 1
				continue
			requestCount[i] = poppedCount
		sortedRequest = sorted(list(requestCount.items()), key=lambda x: -x[1])
		nums.sort(key=lambda x: -x)
		out = 0
		for (n, s) in zip(nums, sortedRequest):
			out += n * s[1]
		return out % (pow(10, 9) + 7)


MODNUM = 10 ** 9 + 7

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		N = len(nums)
		M = len(requests)
		ct = [0] * N
		requests = sorted(requests)
		(i, j) = (0, 0)
		used = []
		for k in range(N):
			while i < M and k >= requests[i][0]:
				(a, b) = requests[i]
				heappush(used, b)
				i += 1
			while len(used) > 0 and k > used[0]:
				heappop(used)
			ct[k] = len(used)
		ct = sorted(ct, reverse=True)
		nums = sorted(nums, reverse=True)
		res = 0
		for (n, c) in zip(nums, ct):
			if c == 0:
				break
			res += n * c
		return res % MODNUM


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		MOD = 10 ** 9 + 7
		nums.sort(reverse=True)
		N = len(nums)
		events = [0] * (N + 1)
		for (start, end) in requests:
			events[start] += 1
			events[end + 1] -= 1
		for i in range(1, len(events)):
			events[i] += events[i - 1]
		res = 0
		events.pop()
		events.sort()
		nums.sort()
		for (num, size) in zip(nums, events):
			res += num * size
		return res % MOD


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		MOD = 10 ** 9 + 7
		tmp = sorted([k for (i, j) in requests for k in [(i, 1), (j + 1, -1)]])
		counter = collections.defaultdict(int)
		last = 0
		now = 0
		for (ind, delta) in tmp:
			counter[now] += ind - last
			last = ind
			now += delta
		nums.sort(reverse=True)
		l = len(nums)
		result = 0
		now = 0
		for (count, num) in sorted(list(counter.items()), reverse=True):
			result += sum(nums[now:now + num]) * count
			now += num
			if now > l:
				break
		return result % MOD


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		if not nums or not requests:
			return 0
		overlaps = [(i, 0) for i in range(len(nums) + 1)]
		for (start, end) in requests:
			overlaps[start] = (overlaps[start][0], overlaps[start][1] + 1)
			overlaps[end + 1] = (overlaps[end + 1][0], overlaps[end + 1][1] - 1)
		for i in range(1, len(overlaps)):
			overlaps[i] = (overlaps[i][0], overlaps[i][1] + overlaps[i - 1][1])
		overlaps.pop()
		overlaps.sort(key=lambda tup: tup[1], reverse=True)
		nums.sort()
		max_permutation = [0] * len(nums)
		for (i, freq) in overlaps:
			max_permutation[i] = nums[-1]
			nums.pop()
		prefix_sum = [max_permutation[0]]
		for i in range(1, len(max_permutation)):
			prefix_sum.append(prefix_sum[i - 1] + max_permutation[i])
		sum = 0
		for (start, end) in requests:
			right = prefix_sum[end]
			left = 0 if start == 0 else prefix_sum[start - 1]
			sum += right - left
		return sum % (10 ** 9 + 7)

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


class Solution:

	def update(self, d, s, e):
		d[s] += 1
		d[e + 1] -= 1

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


class Solution:

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


from itertools import permutations

class Solution:

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


class Solution:

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


import heapq
import math

class Solution:

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


class Solution:

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


class Solution:

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


from collections import deque

class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		nums.sort()
		n = len(nums)
		bit = [0] * (n + 1)

		def query(i):
			s = 0
			while i > 0:
				s += bit[i]
				i -= i & -i
			return s

		def insert(key, value):
			while key <= n:
				bit[key] += value
				key += key & -key
		for request in requests:
			insert(request[0] + 1, 1)
			insert(request[1] + 2, -1)
		vals = sorted([query(i + 1) for i in range(n)])
		return sum((x * y for (x, y) in zip(vals, nums))) % 1000000007


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		req = [0] * (len(nums) + 1)
		for r in requests:
			req[r[0]] += 1
			req[r[1] + 1] -= 1
		for i in range(1, len(req)):
			req[i] += req[i - 1]
		req = sorted(req, reverse=True)
		nums = sorted(nums, reverse=True)
		answer = 0
		for i in range(len(nums)):
			if req[i] == 0 or nums[i] == 0:
				return answer % 1000000007
			answer += req[i] * nums[i]
		return answer % 1000000007


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		N = len(nums)
		take = [False] * N
		MOD = 10 ** 9 + 7
		fenwick = [0] * (N + 1)

		def add(idx, val):
			idx += 1
			while idx <= N:
				fenwick[idx] += val
				idx += idx & -idx

		def sum_(idx):
			idx += 1
			ans = 0
			while idx > 0:
				ans += fenwick[idx]
				idx -= idx & -idx
			return ans

		def range_sum(a, b):
			return sum_(b) - sum_(a - 1)
		for (a, b) in requests:
			add(a, 1)
			add(b + 1, -1)
		occurrences = [0] * N
		for i in range(N):
			occurrences[i] = sum_(i)
		occ = sorted([(v, i) for (i, v) in enumerate(occurrences)], reverse=True)
		nums.sort()
		ans = 0
		for (a, b) in occ:
			if a:
				ans += nums.pop() * a
		return ans % MOD


from collections import defaultdict as dd

class Solution:

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


import collections
import heapq

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from bisect import bisect_left as bl, bisect_right as br

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class BinaryIndexedTree:

	def __init__(self, n):
		n += 1
		self.data = [0] * n
		self.n = n

	def add(self, index, value):
		index += 1
		while index < self.n:
			self.data[index] += value
			index += index & -index

	def prefix(self, index):
		index += 1
		res = 0
		while index:
			res += self.data[index]
			index ^= index & -index
		return res

class Solution:

	def maxSumRangeQuery(self, nums: List[int], query: List[List[int]]) -> int:
		MOD = 10 ** 9 + 7
		n = len(nums)
		BIT = BinaryIndexedTree(n + 1)
		for (l, r) in query:
			BIT.add(l, 1)
			BIT.add(r + 1, -1)
		count_index = []
		for i in range(n):
			count_index.append((BIT.prefix(i), i))
		count_index.sort()
		nums.sort()
		ans = 0
		for ((ct, _), v) in zip(count_index, nums):
			ans += ct * v
			ans %= MOD
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		arr = []
		for (a, b) in requests:
			arr.append([a, -1])
			arr.append([b, 1])
		cnt = 0
		pre = 0
		arr = sorted(arr)
		counter = Counter()
		for (e, fg) in arr:
			if fg == -1:
				counter[cnt] += e - pre
				pre = e
				cnt += 1
			else:
				counter[cnt] += e + 1 - pre
				pre = e + 1
				cnt -= 1
		nums = [-e for e in nums]
		heapq.heapify(nums)
		ans = 0
		for k in sorted(counter.keys())[::-1]:
			cnt = counter[k]
			while cnt != 0:
				cnt -= 1
				x = -heapq.heappop(nums)
				ans += x * k
				ans %= 10 ** 9 + 7
		return ans


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		(m, n) = (len(requests), len(nums))
		ind_count = dict()
		start_count = dict()
		end_count = dict()
		for (s, e) in requests:
			start_count[s] = start_count.get(s, 0) + 1
			end_count[e + 1] = end_count.get(e + 1, 0) + 1
		count = 0
		for ind in range(n):
			count = count + start_count.get(ind, 0) - end_count.get(ind, 0)
			if count > 0:
				ind_count[ind] = count
		inds = sorted(list(ind_count.keys()), key=lambda k: ind_count[k], reverse=True)
		nums = sorted(nums, reverse=True)
		out = 0
		for (i, ind) in enumerate(inds):
			out += ind_count[ind] * nums[i]
		return out % (10 ** 9 + 7)


class Solution:

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


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

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		r_arr = [0] * len(nums)
		MOD = 10 ** 9 + 7
		for r in requests:
			r_arr[r[0]] += 1
			if r[1] < len(r_arr) - 1:
				r_arr[r[1] + 1] -= 1
		idxes = defaultdict(lambda : [])
		idxes[r_arr[0]].append(0)
		for r in range(1, len(r_arr)):
			r_arr[r] += r_arr[r - 1]
			idxes[r_arr[r]].append(r)
		ks = list(idxes.keys())
		ks.sort(reverse=True)
		res_arr = [0] * len(nums)
		nums.sort(reverse=True)
		for k in ks:
			for ele in idxes[k]:
				res_arr[ele] = nums.pop(0)
		res = 0
		for i in range(len(res_arr)):
			res += res_arr[i] * r_arr[i] % MOD
		return res % MOD


class Solution:

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


from functools import cmp_to_key

def cmp(a, b):
	(x1, y1) = a
	(x2, y2) = b
	if x1 < x2:
		return -1
	elif x1 > x2:
		return -1
	elif y1 == 'S':
		return 1
	else:
		return -1

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


MODULO = 10 ** 9 + 7

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		events = [0] * len(nums)
		for (s, e) in requests:
			events[s] += 1
			if e + 1 < len(nums):
				events[e + 1] -= 1
		for i in range(1, len(events)):
			if events[i] == 0:
				events[i] = events[i - 1]
			else:
				events[i] = events[i - 1] + events[i]
		print(events)
		events.sort()
		nums.sort()
		summa = 0
		for (v, n) in zip(events, nums):
			summa = (summa + v * n) % MODULO
		return summa


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


import numpy as np

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from itertools import accumulate
from operator import mul

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from collections import Counter, deque
from itertools import chain
import heapq

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		count = [0] * len(nums)
		for (i, j) in requests:
			count[i] += 1
			if j + 1 < len(count):
				count[j + 1] -= 1
		cur = 0
		for i in range(len(count)):
			count[i] += cur
			cur = count[i]
		return sum((n * c for (n, c) in zip(sorted(nums, reverse=True), sorted(count, reverse=True)))) % (10 ** 9 + 7)


import heapq

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		reqs = [0] * (len(nums) + 1)
		for request in requests:
			reqs[request[0]] += 1
			reqs[request[1] + 1] -= 1
		prev = 0
		reqs.pop()
		for i in range(len(reqs)):
			reqs[i] += prev
			prev = reqs[i]
		nums.sort(reverse=True)
		reqs.sort(reverse=True)
		ret = 0
		M = pow(10, 9) + 7
		for i in range(len(nums)):
			ret = (ret + nums[i] * reqs[i]) % M
		return ret


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from heapq import heappush, heappop

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		n = len(nums)
		count = [0] * (n + 1)
		for request in requests:
			(start, end) = request
			count[start] += 1
			count[end + 1] -= 1
		for i in range(1, n + 1):
			count[i] += count[i - 1]
		answer = 0
		nums.sort()
		c = count[:-1]
		c.sort()
		for (a, b) in zip(nums, c):
			answer += a * b
		mod = 10 ** 9 + 7
		return answer % mod


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


from collections import Counter

class Solution:

	def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
		start = Counter([r[0] for r in requests])
		end = Counter([r[1] for r in requests])
		running_sum = 0
		requests_per_num = []
		for (i, n) in enumerate(nums):
			running_sum += start[i]
			running_sum -= end[i - 1]
			requests_per_num.append(running_sum)
		requests_per_num.sort(reverse=True)
		nums_copy = [n for n in nums]
		nums_copy.sort(reverse=True)
		max_sum = 0
		for (n, r) in zip(nums_copy, requests_per_num):
			max_sum += n * r
		return max_sum % (10 ** 9 + 7)


class Solution:

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


class Solution:

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