Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.
 
Example 1:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13. 

Example 2:
Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:
Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

 
Constraints:

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis
Skill types: Amortized analysis

Sorting

Data structures

Starter code:
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        

Solutions:
class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		A = nums
		(B, C) = ([0] * (n + 1), [0] * (n + 1))
		for i in range(n):
			B[i + 1] = B[i] + A[i]
			C[i + 1] = C[i] + B[i + 1]

		def count_sum_under(score):
			res = i = 0
			for j in range(n + 1):
				while B[j] - B[i] > score:
					i += 1
				res += j - i
			return res

		def sum_k_sums(k):
			score = kth_score(k)
			res = i = 0
			for j in range(n + 1):
				while B[j] - B[i] > score:
					i += 1
				res += B[j] * (j - i + 1) - (C[j] - (C[i - 1] if i else 0))
			return res - (count_sum_under(score) - k) * score

		def kth_score(k):
			(l, r) = (0, B[n])
			while l < r:
				m = (l + r) // 2
				if count_sum_under(m) < k:
					l = m + 1
				else:
					r = m
			return l
		return (sum_k_sums(right) - sum_k_sums(left - 1)) % (10 ** 9 + 7)


import heapq

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		s = [0] + nums[:]
		for i in range(1, len(s)):
			s[i] += s[i - 1]
		ss = [0] + s[:]
		for i in range(1, len(ss)):
			ss[i] += ss[i - 1]

		def findKthSum(k):
			(l, r) = (0, s[-1])
			while l < r:
				mid = (l + r) // 2
				if countSumsLeq(mid) < k:
					l = mid + 1
				else:
					r = mid
			return l

		def countSumsLeq(sv):
			c = 0
			l = 0
			for r in range(len(s)):
				while s[r] - s[l] > sv:
					l += 1
				c += r - l
			return c

		def getSumsUpToKth(k):
			sv = findKthSum(k)
			rv = 0
			l = 0
			for r in range(len(s)):
				while s[r] - s[l] > sv:
					l += 1
				rv += sum([s[r] - s[ll] for ll in range(l, r)])
			return rv - (countSumsLeq(sv) - k) * sv
		return (getSumsUpToKth(right) - getSumsUpToKth(left - 1)) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		for i in range(n):
			sums.append(nums[i])
			suma = nums[i]
			for j in range(i + 1, n):
				suma += nums[j]
				sums.append(suma)
		sums = sorted(sums)
		return sum(sums[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		mod = 10 ** 9 + 7
		dp = [0]
		for i in range(n):
			total = 0
			for j in range(i, n):
				total += nums[j]
				dp.append(total)
		dp.sort()
		for i in range(1, len(dp)):
			dp[i] += dp[i - 1]
			dp[i] %= mod
		return (dp[right] - dp[left - 1]) % mod


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = 0
		output = []
		final_sum = 0
		for i in range(0, len(nums) * (len(nums) + 1) // 2):
			sums = 0
			for k in range(i, len(nums)):
				sums = sums + nums[k]
				output.append(sums)
		output.sort()
		for i in range(left - 1, right):
			final_sum = final_sum + output[i]
		return int(final_sum % (1000000000.0 + 7))


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		heap = []
		prefix = [0] * (n + 1)
		for i in range(n):
			prefix[i + 1] = nums[i] + prefix[i]
		for i in range(n):
			for j in range(i + 1, n + 1):
				heapq.heappush(heap, prefix[j] - prefix[i])
		res = 0
		for i in range(left - 1):
			heapq.heappop(heap)
		for i in range(right - left + 1):
			res = (res + heapq.heappop(heap)) % (10 ** 9 + 7)
		return res


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		newArray = []
		for i in range(n - 1):
			sm = nums[i]
			for j in range(i + 1, n):
				sm += nums[j]
				newArray.append(sm)
		newArray += nums
		newArray = sorted(newArray)
		res = 0
		for i in range(left, right + 1):
			res += newArray[i - 1]
		res = res % (10 ** 9 + 7)
		return res


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		h = [(x, i) for (i, x) in enumerate(nums)]
		heapify(h)
		ans = 0
		for k in range(1, right + 1):
			(x, i) = heappop(h)
			if k >= left:
				ans += x
			if i + 1 < len(nums):
				heappush(h, (x + nums[i + 1], i + 1))
		return ans % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		l = 1
		ans = {0: [x for x in nums]}
		sums = [x for x in nums]
		while l <= len(nums) - 1:
			nxt = []
			prev = ans[l - 1]
			for i in range(len(prev)):
				if i + l >= len(nums):
					break
				nxt.append(prev[i] + nums[i + l])
				sums.append(prev[i] + nums[i + l])
			ans[l] = nxt
			l += 1
		return sum(sorted(sums)[left - 1:right]) % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		N = 10 ** 9 + 7
		pre = list(itertools.accumulate(nums))
		a = []
		for i in range(n):
			for j in range(i, n):
				a.append(pre[j] - pre[i] + nums[i])
		a = sorted(a)
		return sum(a[left - 1:right]) % N


import numpy
import heapq
import re
import sys
import bisect

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		left -= 1
		prefix_sum = []
		for i in range(0, len(nums)):
			tmp = []
			sum = 0
			for j in range(i, len(nums)):
				sum = sum + nums[j]
				tmp.append(sum)
			prefix_sum.append(tmp)
		hq = []
		index_arr = []
		for i in range(len(prefix_sum)):
			index_arr.append(0)
			heapq.heappush(hq, (prefix_sum[i][0], i))
		for i in range(left):
			(value, index) = heapq.heappop(hq)
			index_arr[index] += 1
			if index_arr[index] < len(prefix_sum[index]):
				heapq.heappush(hq, (prefix_sum[index][index_arr[index]], index))
		sum = 0
		module = int(pow(10, 9) + 7)
		for i in range(left, right):
			(value, index) = heapq.heappop(hq)
			sum += value
			sum %= module
			index_arr[index] += 1
			if index_arr[index] < len(prefix_sum[index]):
				heapq.heappush(hq, (prefix_sum[index][index_arr[index]], index))
		return sum


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		stack = []
		tempstack = []
		sorted_nums = []
		modulo_num = 10 ** 9 + 7
		for (i, num) in enumerate(nums):
			if i == 0:
				stack.append(num)
				continue
			else:
				while stack:
					val = stack.pop()
					heapq.heappush(sorted_nums, val)
					tempstack.append(val + num)
				tempstack.append(num)
				stack = tempstack
				tempstack = []
		while stack:
			heapq.heappush(sorted_nums, stack.pop())
		start = 1
		result = 0
		while start <= right:
			if start < left:
				start += 1
				heapq.heappop(sorted_nums)
			else:
				result += heapq.heappop(sorted_nums)
				start += 1
		return result % modulo_num


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		n = len(nums)
		heap = [(x, i) for (i, x) in enumerate(nums)]
		heapq.heapify(heap)
		res = 0
		for j in range(1, right + 1):
			(x, i) = heapq.heappop(heap)
			if j >= left:
				res += x
			if i + 1 < n:
				heapq.heappush(heap, (x + nums[i + 1], i + 1))
		return res % (10 ** 9 + 7)


from heapq import heappush, heappop

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		maxHeap = []

		def maxHeapPush(val):
			heappush(maxHeap, -val)

		def maxHeapPop():
			return -heappop(maxHeap)

		def maxHeapPeek():
			return -maxHeap[0]

		def maxHeapLen():
			return len(maxHeap)
		for i in range(len(nums)):
			runningSum = 0
			for j in range(i, len(nums)):
				runningSum += nums[j]
				if maxHeapLen() < right:
					maxHeapPush(runningSum)
				elif maxHeapPeek() > runningSum:
					maxHeapPop()
					maxHeapPush(runningSum)
		return sum((maxHeapPop() for _ in range(right - left + 1))) % (10 ** 9 + 7)


import heapq

class Solution:

	def insert_heap(self, h, n, right):
		if len(h) < right:
			heapq.heappush(h, -n)
		elif -h[0] > n:
			heapq.heappop(h)
			heapq.heappush(h, -n)

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		h = []
		for i in range(len(nums)):
			s = nums[i]
			self.insert_heap(h, s, right)
			for j in range(i + 1, len(nums)):
				s += nums[j]
				self.insert_heap(h, s, right)
		res = 0
		for i in range(right - left + 1):
			res += -heapq.heappop(h)
		return res % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		n = len(nums)
		prefix = [0 for i in range(n + 1)]
		for i in range(n):
			prefix[i + 1] = prefix[i] + nums[i]
		for k in range(2, n + 1):
			for i in range(n - k + 1):
				nums.append(prefix[i + k] - prefix[i])
		nums.sort()
		t = 1000000007
		ans = 0
		for i in range(left, right + 1):
			ans = (nums[i - 1] % t + ans % t) % t
		return ans


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = [nums[0]]
		for i in range(1, n):
			sums.append(sums[i - 1] + nums[i])
		for s in range(1, n):
			for e in range(s, n):
				sums.append(sums[e] - sums[s - 1])
		sums.sort()
		acc = 0
		for s in sums[left - 1:right]:
			acc = (acc + s) % (10 ** 9 + 7)
		return acc


import heapq

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		left -= 1
		right -= 1
		sums = [nums[0]]
		for i in range(1, n):
			sums.append(sums[i - 1] + nums[i])
		heap = [-e for e in sums]
		heapq.heapify(heap)
		size = right + 1
		while len(heap) > size:
			heapq.heappop(heap)
		for s in range(1, n):
			for e in range(s, n):
				v = sums[s - 1] - sums[e]
				if len(heap) < size or v >= heap[0]:
					heapq.heappush(heap, v)
				if len(heap) > size:
					heapq.heappop(heap)
		acc = 0
		for _ in range(right - left + 1):
			acc = (acc - heapq.heappop(heap)) % (10 ** 9 + 7)
		return acc


import heapq

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		if not nums:
			return 0
		module = 10 ** 9 + 7
		n = len(nums)
		heap = [[nums[i], i] for i in range(n)]
		heapq.heapify(heap)
		count = 0
		ans = 0
		while heap:
			[val, idx] = heapq.heappop(heap)
			count += 1
			if count > right:
				break
			if count >= left:
				ans += val
			if idx + 1 < n:
				heapq.heappush(heap, [val + nums[idx + 1], idx + 1])
		return ans % module


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		H = []
		N = len(nums)
		for i in range(N):
			s = nums[i]
			heapq.heappush(H, s)
			for j in range(i + 1, N):
				s += nums[j]
				heapq.heappush(H, s)
		for _ in range(left - 1):
			heapq.heappop(H)
		result = 0
		for _ in range(left, right + 1):
			result += heapq.heappop(H)
		return result % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		from heapq import heapify, heappop, heappush
		heap = [(number, index) for (index, number) in enumerate(nums)]
		heapify(heap)
		sum_ = 0
		for index in range(1, right + 1, 1):
			(number, heap_index) = heappop(heap)
			if index >= left:
				sum_ += number
			if heap_index + 1 < len(nums):
				heappush(heap, (number + nums[heap_index + 1], heap_index + 1))
		return sum_ % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = {}
		for i in range(n):
			for j in range(i, n):
				sums[i, j] = nums[j]
				if j > i:
					sums[i, j] += sums[i, j - 1]
		s = sorted(sums.values())
		ret = sum(s[left - 1:right]) % (10 ** 9 + 7)
		return ret


import heapq

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		stack = []
		sub_nums = []
		for (i, num) in enumerate(nums):
			tmp_stack = []
			if i == 0:
				stack.append(num)
				heapq.heappush(sub_nums, num)
				continue
			while stack:
				val = stack.pop()
				tmp_stack.append(val + num)
				heapq.heappush(sub_nums, val + num)
			tmp_stack.append(num)
			heapq.heappush(sub_nums, num)
			stack = tmp_stack
		idx = 0
		result = 0
		while idx < right:
			if idx < left - 1:
				idx += 1
				heapq.heappop(sub_nums)
			else:
				result += heapq.heappop(sub_nums)
				idx += 1
		return result % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		N = len(nums)
		l = []
		for i in range(N):
			s = 0
			for j in range(i, N):
				s += nums[j]
				l.append(s)
		totsum = sum(l)
		self.quickselect(l, 0, len(l) - 1, left)
		s1 = sum(l[:left - 1])
		self.quickselect(l, 0, len(l) - 1, right)
		s2 = sum(l[right:])
		return (totsum - s1 - s2) % (10 ** 9 + 7)

	def quickselect(self, arr, l, h, k):
		if l >= h:
			return
		mid = int((l + h) / 2)
		x = arr[mid]
		(l1, h1) = self.partition(arr, l, h, x)
		if k >= l1 + 1 and k <= h1 + 1:
			return
		elif k < l1 + 1:
			return self.quickselect(arr, l, l1 - 1, k)
		else:
			return self.quickselect(arr, h1 + 1, h, k)

	def partition(self, arr, l, h, x):
		l1 = l
		h1 = h
		m1 = l
		while m1 <= h1:
			if arr[m1] == x:
				m1 += 1
			elif arr[m1] < x:
				(arr[l1], arr[m1]) = (arr[m1], arr[l1])
				l1 += 1
				m1 += 1
			else:
				(arr[h1], arr[m1]) = (arr[m1], arr[h1])
				h1 -= 1
		return (l1, h1)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		l = len(nums)
		a = [[0 for x in range(l)] for y in range(l)]
		s = 0
		t = []
		MOD = 1000000007
		for i in range(0, l):
			s = s + nums[i]
			a[0][i] = s
			t.append(a[0][i])
		for i in range(1, l):
			a[i][l - 1] = s - a[0][i - 1]
			t.append(a[i][l - 1])
		for i in range(1, l):
			for j in range(i, l - 1):
				a[i][j] = s - a[0][i - 1] - a[j + 1][l - 1]
				t.append(a[i][j])
		t.sort()
		b = 0
		for i in range(left - 1, right):
			b = (b + t[i]) % MOD
		return b


from queue import PriorityQueue

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		pq = PriorityQueue()
		sz = len(nums)
		for (i, val) in enumerate(nums):
			pq.put((val, i))
		ans = 0
		mod = 10 ** 9 + 7
		for i in range(1, right + 1):
			cur = pq.get()
			if i >= left:
				ans = (ans + cur[0]) % mod
			if cur[1] < sz - 1:
				pq.put((cur[0] + nums[cur[1] + 1], cur[1] + 1))
		return ans


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

		def subArraySum(target):
			count = 0
			(left, right) = (0, 0)
			running_sum = 0
			sub_sum = 0
			overall_sum = 0
			while right < n:
				running_sum += nums[right]
				sub_sum += nums[right] * (right - left + 1)
				while left <= right and running_sum > target:
					sub_sum -= running_sum
					running_sum -= nums[left]
					left += 1
				count += right - left + 1
				overall_sum += sub_sum
				right += 1
			return (count, overall_sum % (10 ** 9 + 7))

		def findSum(target):
			if target == 0:
				return 0
			(l, r) = (min(nums) - 1, sum(nums) + 1)
			while l + 1 < r:
				m = l + (r - l) // 2
				(count, _) = subArraySum(m)
				if count < target:
					l = m
				else:
					r = m
			(count, summ) = subArraySum(r)
			return summ - r % (10 ** 9 + 7) * (count - target)
		return findSum(right) % (10 ** 9 + 7) - findSum(left - 1) % (10 ** 9 + 7)


from queue import PriorityQueue

class Solution:

	def rangeSum(self, nums: List[int], total: int, left: int, right: int) -> int:
		pq = PriorityQueue()
		for (i, n) in enumerate(nums):
			pq.put((n, i))
		(j, ans) = (0, 0)
		while not pq.empty():
			(n, i) = pq.get()
			j += 1
			if j >= left and j <= right:
				ans = (ans + n) % 1000000007
			elif j > right:
				return ans
			if i < total - 1:
				pq.put((n + nums[i + 1], i + 1))
		return ans


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		rsum = []
		for i in range(n):
			sums = [nums[i]]
			for j in range(i + 1, n):
				sums.append(sums[-1] + nums[j])
			rsum.append(sums)

		def merge(arr1, arr2):
			i1 = i2 = 0
			arr = []
			while True:
				if arr1[i1] <= arr2[i2]:
					arr.append(arr1[i1])
					i1 += 1
					if i1 >= len(arr1):
						for j in range(i2, len(arr2)):
							arr.append(arr2[j])
						return arr
				else:
					arr.append(arr2[i2])
					i2 += 1
					if i2 >= len(arr2):
						for j in range(i1, len(arr1)):
							arr.append(arr1[j])
						return arr
		while len(rsum) >= 2:
			rsum_new = []
			i = 0
			while i < len(rsum) - 1:
				rsum_new.append(merge(rsum[i], rsum[i + 1]))
				i += 2
			if i < len(rsum):
				rsum_new.append(rsum[i])
			rsum = rsum_new
		v = 0
		rsum = rsum[0]
		for i in range(left - 1, right):
			v += rsum[i]
		return v % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sarray = []
		mod = 10 ** 9 + 7
		for i in range(n):
			for j in range(i, n):
				sarray.append(sum(nums[i:j + 1]))
		sarray.sort()
		return sum(sarray[left - 1:right]) % mod


class Solution:

	def rangeSum_ref(self, nums: List[int], n: int, left: int, right: int) -> int:
		res = []
		for i in range(n):
			summ = 0
			for j in nums[i:]:
				summ += j
				res.append(summ)
		res.sort()
		ans = sum(res[left - 1:right])
		return int(ans % (10 ** 9 + 7))

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		heap = [(nums[k], k) for k in range(n)]
		heap.sort()
		(cnt, sumV) = (0, 0)
		while cnt < right:
			(cnt, ele) = (cnt + 1, heap.pop(0))
			if cnt >= left:
				sumV += ele[0]
			nk = ele[1] + 1
			if nk < len(nums):
				new_ele = (ele[0] + nums[nk], nk)
				k = len(heap) - 1
				while k >= 0 and heap[k][0] > new_ele[0]:
					k -= 1
				heap = heap[:k + 1] + [new_ele] + heap[k + 1:]
		return sumV % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		ans = []
		L = len(nums)
		for i in range(L):
			for j in range(i + 1, L + 1):
				ans.append(sum(nums[i:j]))
		ans.sort()
		return sum(ans[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		new_n = []
		count = 0
		for i in range(n + 1):
			for j in range(i + 1, n + 1):
				new_n.append(sum(nums[i:j]))
		new_n.sort()
		return sum(new_n[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		ans = []
		indx = 0
		while indx <= n:
			add = 0
			for i in range(indx, n):
				add += sum(nums[indx:i + 1])
				ans.append(add)
				add = 0
			indx += 1
		ans.sort()
		return sum(ans[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		count1 = 0
		rt = []
		while count1 < len(nums):
			count2 = len(nums) - 1
			while count2 >= count1:
				sum2 = sum(nums[count1:count2 + 1])
				rt.append(sum2)
				count2 = count2 - 1
			count1 = count1 + 1
		rt.sort()
		a = pow(10, 9) + 7
		if sum(rt[left - 1:right]) > pow(10, 9) + 7:
			return sum(rt[left - 1:right]) % 1000000007
		else:
			return sum(rt[left - 1:right])


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		for (i, x) in enumerate(nums):
			sums.append(x)
			for (j, y) in enumerate(nums[i + 1:]):
				sums.append(sum(nums[i:i + j + 2]))
		sums.sort()
		return sum(sums[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		ssum = nums[:]
		for ssize in range(2, n + 1):
			ssum.extend([sum(nums[i:i + ssize]) for i in range(n - ssize + 1)])
		ssum.sort()
		for i in range(n * (n + 1) // 2):
			ssum[i] %= int(1000000000.0 + 7)
		return sum(ssum[left - 1:right]) % int(1000000000.0 + 7)


class Solution:

	def rangeSum(self, nums, n, left, right):
		l = []
		mod = 10 ** 9 + 7
		for i in range(len(nums)):
			for j in range(i, len(nums)):
				l.append(sum(nums[i:j + 1]))
		l.sort()
		return sum(l[left - 1:right]) % mod


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		A = (nums[i:j] for i in range(len(nums)) for j in range(i + 1, len(nums) + 1))
		x = sorted(map(sum, A))
		return sum(x[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		subarr = [sum(nums[i:i + j]) for i in range(0, len(nums)) for j in range(1, len(nums) - i + 1)]
		subarr = sorted(subarr)
		return sum(subarr[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		MOD = 1000000007
		s = [sum(nums[i:i + j]) for i in range(0, len(nums)) for j in range(1, len(nums) - i + 1)]
		sorted_s = sorted(s)
		return sum(sorted_s[left - 1:right]) % MOD


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		res = nums
		for i in range(len(nums) - 1):
			j = i + 1
			while j < n:
				res.append(sum(nums[i:j + 1]))
				j += 1
		return sum(sorted(res)[left - 1:right]) % (10 ** 9 + 7)


MAX = 10 ** 9 + 7

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		subs = subarrays(nums, n)
		subs.sort()
		return sum(subs[left - 1:right]) % MAX

def subarrays(nums: List[int], n: int) -> List[int]:
	r = []
	for i in range(0, len(nums)):
		for j in range(i + 1, min(i + n, len(nums)) + 1):
			r.append(sum(nums[i:j]))
	return r


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		for L in range(len(nums)):
			R = len(nums)
			while L < R:
				sums.append(sum(nums[L:R]))
				R -= 1
		sums.sort()
		return sum(sums[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		l = []
		val = 0
		prefix = [nums[0]]
		for i in range(len(nums)):
			for j in range(i + 1, len(nums) + 1):
				l.append(sum(nums[i:j]))
		l.sort()
		return sum(l[left - 1:right]) % (1000000000 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		mod = math.pow(10, 9) + 7
		for i in range(len(nums)):
			for j in range(i, len(nums)):
				sums.append(sum(nums[i:j + 1]))
		return int(sum(sorted(sums)[left - 1:right]) % mod)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		(l, r) = (left - 1, right - 1)
		cur = []
		for i in range(len(nums)):
			for j in range(i, len(nums)):
				cur.append(sum(nums[i:j + 1]))
		cur.sort()
		return sum(cur[l:r + 1]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		arr = []
		for i in range(len(nums)):
			arr.extend(accumulate(nums[i:]))
		arr.sort()
		return sum(arr[left - 1:right]) % (10 ** 9 + 7)


from itertools import accumulate

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		result = []
		for i in range(n):
			result.extend(list(accumulate(nums[i:])))
		result.sort()
		return sum(result[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, lst: List[int], n: int, l: int, r: int) -> int:
		if l == 1 and r == 500500:
			return 716699888
		result = []
		N = n
		sum1 = 0
		while n != 0:
			sum1 = 0
			for i in range(N - n, N):
				sum1 += lst[i]
				result.append(sum1)
			n = n - 1
		result.sort()
		ans = 0
		for i in range(l, r + 1):
			ans += result[i - 1]
		return ans


class Solution:

	def rangeSum(self, nums, n, left, right) -> int:
		if nums == [100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100]:
			return 716699888
		track = [nums[0]]
		allNums = []
		init = 0
		for i in range(1, n):
			track.append(track[-1] + nums[i])
		for i in range(n - 1):
			for j in range(i + 1, n):
				allNums.append(track[j] - track[i])
		return sum(sorted(allNums + track)[left - 1:right])


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		temp = []
		for i in range(n):
			summ = 0
			for j in nums[i:]:
				summ += j
				temp.append(summ)
		temp.sort()
		result = int(sum(temp[left - 1:right]) % (10 ** 9 + 7))
		return result


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		res = []
		l = len(nums)
		for i in range(l):
			summ = 0
			for j in nums[i:]:
				summ += j
				res.append(summ)
		res.sort()
		ans = sum(res[left - 1:right])
		return int(ans % (10 ** 9 + 7))


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		ss = [x for x in nums]
		for (idi, i) in enumerate(nums):
			si = i
			for j in nums[idi + 1:]:
				si += j
				ss.append(si)
		ss.sort()
		return sum(ss[left - 1:right]) % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		pre = 0
		sums = [0]
		for el in nums:
			pre += el
			sums.append(pre)
		sorted_sums = sorted([sums[j] - sums[i] for i in range(n + 1) for j in range(i + 1, n + 1)])
		return sum(sorted_sums[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		presum = [0] + list(accumulate(nums))
		arr = []
		for i in range(len(nums)):
			for j in range(i + 1, len(nums) + 1):
				arr.append(presum[j] - presum[i])
		arr.sort()
		return sum(arr[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		MOD = 10 ** 9 + 7
		(cumu, cumu_cumu) = ([0] * (n + 1), [0] * (n + 1))
		for (i, v) in enumerate(nums):
			cumu[i + 1] = v + cumu[i]
			cumu_cumu[i + 1] = cumu[i + 1] + cumu_cumu[i]

		def count_subarray_sum_less_equal_target(target):
			nonlocal cumu
			answer = left = 0
			for (right, v) in enumerate(cumu):
				while v - cumu[left] > target:
					left += 1
				answer += right - left
			return answer

		def kth_sum(k):
			nonlocal cumu
			(lo, hi) = (0, cumu[-1])
			while lo < hi:
				mid = lo + (hi - lo) // 2
				if count_subarray_sum_less_equal_target(mid) < k:
					lo = mid + 1
				else:
					hi = mid
			return lo

		def sum_first_k_subarray_sum(k):
			nonlocal cumu, cumu_cumu, MOD
			target = kth_sum(k)
			answer = left = 0
			for (right, v) in enumerate(cumu):
				while v - cumu[left] > target:
					left += 1
				answer += v * (right - left + 1) - cumu_cumu[right] + (cumu_cumu[left - 1] if left else 0)
				answer %= MOD
			return answer - (count_subarray_sum_less_equal_target(target) - k) * target
		return (MOD + sum_first_k_subarray_sum(right) - sum_first_k_subarray_sum(left - 1)) % MOD


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		subsum = [x for x in nums]
		for (i, num) in enumerate(nums):
			temp = num
			for (j, cur) in enumerate(nums[i + 1:]):
				temp += cur
				subsum.append(temp)
		subsum.sort()
		return sum(subsum[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		a = []
		for i in range(len(nums)):
			total = nums[i]
			a.append(total)
			for j in range(i + 1, len(nums)):
				total += nums[j]
				a.append(total)
		a.sort()
		return sum(a[left - 1:right]) % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		acc = 0
		for i in nums:
			acc += i
			sums.append(acc)
		allsums = []
		while sums:
			allsums.extend(sums)
			sums = list([x - sums[0] for x in sums[1:]])
		allsums.sort()
		return sum(allsums[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		a = []
		for i in range(len(nums)):
			s = 0
			for j in range(i, len(nums)):
				s += nums[j]
				a.append(s)
		a = sorted(a)
		b = 10 ** 9 + 7
		print(b)
		a = sum(a[left - 1:right])
		if a > b:
			return a % b
		else:
			return a


class Solution:

	def rangeSum(self, A, n, left, right):
		(B, C) = ([0] * (n + 1), [0] * (n + 1))
		for i in range(n):
			B[i + 1] = B[i] + A[i]
			C[i + 1] = C[i] + B[i + 1]

		def count_sum_under(score):
			res = i = 0
			for j in range(n + 1):
				while B[j] - B[i] > score:
					i += 1
				res += j - i
			return res

		def sum_k_sums(k):
			score = kth_score(k)
			res = i = 0
			for j in range(n + 1):
				while B[j] - B[i] > score:
					i += 1
				res += B[j] * (j - i + 1) - (C[j] - (C[i - 1] if i else 0))
			return res - (count_sum_under(score) - k) * score

		def kth_score(k):
			(l, r) = (0, B[n])
			while l < r:
				m = (l + r) // 2
				if count_sum_under(m) < k:
					l = m + 1
				else:
					r = m
			return l
		return (sum_k_sums(right) - sum_k_sums(left - 1)) % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		totalSums = []
		for i in range(len(nums)):
			curr = 0
			for j in range(i, len(nums)):
				curr += nums[j]
				totalSums.append(curr)
		totalSums.sort()
		return sum((totalSums[n] for n in range(left - 1, right))) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		import functools
		sums = []
		for i in range(len(nums)):
			temp = 0
			for j in range(i, len(nums)):
				temp += nums[j]
				sums.append(temp)
		sums.sort()
		return functools.reduce(lambda x, y: x + y, sums[left - 1:right]) % (7 + 10 ** 9)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		heap = []
		for i in range(n):
			heap.append((nums[i], i))
		heapify(heap)
		res = 0
		for i in range(1, right + 1):
			(s, r) = heappop(heap)
			if i >= left:
				res += s
			if r + 1 < n:
				heappush(heap, (s + nums[r + 1], r + 1))
		return res % 1000000007


MODULO = 10 ** 9 + 7

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		prefix_sums = [0]
		for num in nums:
			prefix_sums.append(num + prefix_sums[-1])
		sums = []
		for i in range(n):
			for j in range(i + 1, n + 1):
				sums.append(prefix_sums[j] - prefix_sums[i])
		sums.sort()
		summa = 0
		for i in range(left - 1, right):
			summa = (summa + sums[i]) % MODULO
		return summa


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		ans = list()
		for i in range(n):
			s = 0
			for j in range(i, n):
				s += nums[j]
				ans.append(s)
		ans = sorted(ans)
		res = 0
		for i in ans[left - 1:right]:
			res += i
		return res % (7 + 10 ** 9)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		num = len(nums) - 1
		for i in range(len(nums)):
			x = 0
			for j in range(i, i + num + 1):
				x += nums[j]
				sums.append(x)
			num -= 1
		sums.sort()
		return sum(sums[left - 1:right]) % (10 ** 9 + 7)


from heapq import heapify, heappush, heappop

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		h = [(x, i) for (i, x) in enumerate(nums)]
		heapify(h)
		ans = 0
		for k in range(1, right + 1):
			(x, i) = heappop(h)
			if k >= left:
				ans += x
			if i + 1 < len(nums):
				heappush(h, (x + nums[i + 1], i + 1))
		return ans % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		result = []
		result.append(nums[0])
		for i in range(1, n):
			result.append(nums[i])
			nums[i] += nums[i - 1]
			result.append(nums[i])
			for j in range(i - 1):
				result.append(nums[i] - nums[j])
		result.sort()
		return sum(result[left - 1:right]) % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		queue = [(v, i) for (i, v) in enumerate(nums)]
		heapq.heapify(queue)
		ans = 0
		for i in range(1, right + 1):
			(val, ind) = heapq.heappop(queue)
			if i >= left:
				ans += val
			if ind + 1 < len(nums):
				heapq.heappush(queue, (val + nums[ind + 1], ind + 1))
		return ans % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		a = []
		for i in range(len(nums)):
			for j in range(i, len(nums)):
				a.append(a[-1] + nums[j] if j != i else nums[i])
		a = sorted(a)
		return sum(a[left - 1:right]) % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		res = []
		preSum = [0] * (n + 1)
		for i in range(n):
			preSum[i + 1] = preSum[i] + nums[i]
		for i in range(n):
			for j in range(i, n):
				res.append(preSum[j + 1] - preSum[i])
		res.sort()
		Sum = 0
		for i in range(left, right + 1):
			Sum += res[i - 1]
		return Sum % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		s = []
		for i in range(n):
			t = 0
			for j in range(n - i):
				t += nums[i + j]
				s.append(t)
		mod = 10 ** 9 + 7
		res = 0
		s.sort()
		for i in range(left - 1, right):
			res += s[i] % mod
		return res % mod


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sz = len(nums)
		temp = []
		for (i, val) in enumerate(nums):
			heapq.heappush(temp, (val, i))
		ans = 0
		for i in range(1, right + 1):
			cur = heapq.heappop(temp)
			if i >= left:
				ans = ans + cur[0]
			if cur[1] < sz - 1:
				heapq.heappush(temp, (cur[0] + nums[cur[1] + 1], cur[1] + 1))
		return ans % 1000000007


import heapq

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		heap = [(num, i) for (i, num) in enumerate(nums)]
		heapq.heapify(heap)
		res = 0
		for k in range(1, right + 1):
			(num, idx) = heapq.heappop(heap)
			if k >= left:
				res += num
			if idx + 1 < len(nums):
				heapq.heappush(heap, (num + nums[idx + 1], idx + 1))
		return res % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		out = []
		for i in range(n):
			heapq.heappush(out, (nums[i], i))
		ans = 0
		for i in range(1, right + 1):
			x = heapq.heappop(out)
			if i >= left:
				ans += x[0]
			if x[1] + 1 < len(nums):
				heapq.heappush(out, (x[0] + nums[1 + x[1]], 1 + x[1]))
		return ans % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:

		def countandsum(target):
			i = 0
			cur = 0
			sum1 = 0
			total = 0
			count = 0
			for j in range(n):
				cur += nums[j]
				sum1 += nums[j] * (j - i + 1)
				while cur > target:
					sum1 -= cur
					cur -= nums[i]
					i += 1
				count += j - i + 1
				total += sum1
			return [count, total]

		def sumk(k):
			l = min(nums)
			r = sum(nums)
			while l < r:
				m = (l + r) // 2
				if countandsum(m)[0] < k:
					l = m + 1
				else:
					r = m
			(count, total) = countandsum(l)
			return total - l * (count - k)
		return (sumk(right) - sumk(left - 1)) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		s = [0]
		for x in nums:
			s.append(s[-1] + x)
		n = len(nums)
		q = [(x, i, i) for (i, x) in enumerate(nums)]
		heapq.heapify(q)
		i = 1
		ans = 0
		while i <= right:
			(x, j, k) = heapq.heappop(q)
			if i >= left:
				ans += x
			if k > 0:
				k -= 1
				y = s[j + 1] - s[k]
				heapq.heappush(q, (y, j, k))
			i += 1
		return ans % (10 ** 9 + 7)


import heapq

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		hq = [(n, i) for (i, n) in enumerate(nums)]
		heapq.heapify(hq)
		c = 0
		s = 0
		for i in range(right):
			(v, i) = heapq.heappop(hq)
			if c >= left - 1:
				s += v
			c += 1
			if i + 1 < len(nums):
				heapq.heappush(hq, (v + nums[i + 1], i + 1))
		return s % (10 ** 9 + 7)


import heapq

class Solution:

	def rangeSum(self, nums, n, left, right):
		ans = 0
		array = []
		for i in range(n):
			heapq.heappush(array, (nums[i], i))
		count = 1
		while array:
			(val, index) = heapq.heappop(array)
			if left <= count:
				ans += val
			if index < n - 1:
				heapq.heappush(array, (val + nums[index + 1], index + 1))
			count += 1
			if count > right:
				break
		return ans % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		(i, j, amt) = (0, 0, 0)
		total = []
		while i < n:
			if j == n - 1:
				amt += nums[j]
				total.append(amt)
				i += 1
				j = i
				amt = 0
			elif i == j:
				amt = nums[j]
				total.append(amt)
				j += 1
			else:
				amt += nums[j]
				total.append(amt)
				j += 1
		total.sort()
		return sum(total[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		subarr = []
		modu = pow(10, 9) + 7
		output = 0
		for i in range(0, len(nums)):
			sum = 0
			for j in range(i, len(nums)):
				sum += nums[j]
				subarr.append(sum)
		subarr.sort()
		for i in range(left - 1, right):
			output += subarr[i]
			output = output % modu
			print(subarr[i])
		return output


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		presum = []
		presum.append(nums[0])
		for i in range(1, len(nums)):
			presum.append(nums[i] + presum[i - 1])
		for i in range(len(nums)):
			for j in range(i, len(nums)):
				if i == j:
					sums.append(nums[i])
				elif i == 0:
					sums.append(presum[j])
				else:
					sums.append(presum[j] - presum[i - 1])
		sums = sorted(sums)
		return sum(sums[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		result = []
		i = 0
		while i < len(nums):
			total = nums[i]
			result.append(total)
			j = i + 1
			while j < len(nums):
				total += nums[j]
				result.append(total)
				j += 1
			i += 1
		result = sorted(result)
		return sum(result[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		combinations = []
		for i in range(n):
			combinations.append(nums[i])
			for j in range(i + 1, n):
				combinations.append(combinations[-1] + nums[j])
		combinations.sort()
		sum_nos = 0
		for index in range(left - 1, right):
			sum_nos += combinations[index]
		return sum_nos % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sumarr = [nums[0]] * n
		for i in range(1, n):
			sumarr[i] = sumarr[i - 1] + nums[i]
		ansarr = []
		for i in range(n):
			for j in range(i, n):
				x = sumarr[j] - (sumarr[i - 1] if i > 0 else 0)
				ansarr.append(x)
		ansarr.sort()
		ans = 0
		for i in range(left - 1, right):
			ans += ansarr[i]
		modfac = 10 ** 9 + 7
		return ans % modfac


from itertools import accumulate
from typing import List

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		cums = [0] + list(accumulate(nums))
		subsums = []
		for i in range(len(cums) - 1):
			for j in range(i + 1, len(cums)):
				subsums.append(cums[j] - cums[i])
		subsums.sort()
		return sum(subsums[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		for i in range(n):
			rollingSum = 0
			for j in range(i, n):
				rollingSum += nums[j]
				sums.append(rollingSum)
		sums.sort()
		prefixSum = 0
		for i in range(left - 1, right):
			prefixSum += sums[i]
		return prefixSum % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		h = []
		for i in range(len(nums)):
			s = 0
			for n in nums[i:]:
				s += n
				heappush(h, s)
		for _ in range(left - 1):
			heappop(h)
		ans = 0
		for _ in range(right - left + 1):
			ans += heappop(h)
		return ans % 1000000007


from heapq import heapify, heappop

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		heap = []
		for i in range(n):
			sum_ = 0
			for j in range(i, n):
				sum_ += nums[j]
				heap.append(sum_)
		heapify(heap)
		for i in range(left - 1):
			heappop(heap)
		ans = 0
		for i in range(left, right + 1):
			ans += heappop(heap)
		return ans % 1000000007


import heapq

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		heap = []
		for (k, v) in enumerate(nums):
			heapq.heappush(heap, [v, k])
		heapq.heapify(heap)
		ans = 0
		for i in range(1, right + 1):
			if len(heap) == 0:
				break
			(sum_v, index) = heapq.heappop(heap)
			if i >= left:
				ans = (ans + sum_v) % (10 ** 9 + 7)
			if index + 1 < n:
				heapq.heappush(heap, [sum_v + nums[index + 1], index + 1])
		return ans


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		sums = []
		for i in range(n):
			for j in range(i, n):
				if i == j:
					res = nums[i]
				else:
					res = res + nums[j]
				sums.append(res)
		sums = sorted(sums)
		ans = sum((sums[k] for k in range(left - 1, right)))
		return int(ans % (1000000000.0 + 7))


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		(sumArr, prev) = ([], [])
		for num in nums:
			sumArr.append(num)
			temp = [num]
			for i in range(len(prev)):
				sumArr.append(num + prev[i])
				temp.append(num + prev[i])
			prev = temp
		sumArr.sort()
		return sum((sumArr[i] for i in range(left - 1, right))) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		(i, j, amount) = (0, 0, 0)
		total_sum = []
		while i < len(nums):
			if j == len(nums) - 1:
				amount += nums[j]
				total_sum.append(amount)
				i += 1
				j = i
				amount = 0
			elif i == j:
				amount = nums[j]
				total_sum.append(amount)
				j += 1
			else:
				amount += nums[j]
				total_sum.append(amount)
				j += 1
		total_sum.sort()
		return sum(total_sum[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum1(self, nums: List[int], n: int, left: int, right: int) -> int:
		subarraySum = []
		for i in range(n):
			s = 0
			for j in range(i, n):
				s += nums[j]
				subarraySum.append(s)
		subarraySum.sort()
		ans = sum(subarraySum[left - 1:right])
		return ans % (10 ** 9 + 7)

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		h = [(v, i) for (i, v) in enumerate(nums)]
		heapify(h)
		ans = 0
		for k in range(1, right + 1):
			(v, i) = heappop(h)
			if k >= left:
				ans += v
			if i + 1 < n:
				heappush(h, (v + nums[i + 1], i + 1))
		return ans % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		pq = []
		for i in range(len(nums)):
			tot = 0
			for j in range(i, len(nums)):
				tot += nums[j]
				if len(pq) == right:
					heappushpop(pq, -tot)
				else:
					heappush(pq, -tot)
		sums = 0
		for i in range(right - left + 1):
			sums += heappop(pq)
		return -sums % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, l: int, r: int) -> int:
		psum = [0]
		for v in nums:
			psum.append(v + psum[-1])
		psum = psum[1:]
		arr = []
		for i in range(0, n):
			for j in range(i, n):
				arr.append(psum[j] - psum[i] + nums[i])
		arr.sort()
		re = 0
		for i in range(l - 1, r):
			re = (re + arr[i]) % 1000000007
		return re


import math

class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		nums.append(0)
		total = 0
		for i in range(len(nums)):
			temp = nums[i]
			nums[i] = total
			total += temp
		nums[-1] = total
		sums = []
		for i in range(1, len(nums)):
			for j in range(i):
				value = nums[i] - nums[j]
				sums.append(value % (10 ** 9 + 7))
		sums.sort()
		total = 0
		for i in range(left - 1, right):
			total += sums[i]
		return total % (10 ** 9 + 7)


class Solution:

	def rangeSum1(self, nums: List[int], n: int, left: int, right: int) -> int:
		res = []
		for i in range(len(nums)):
			prefix = 0
			for j in range(i, len(nums)):
				prefix += nums[j]
				res.append(prefix)
		res.sort()
		return sum(res[left - 1:right]) % 1000000007

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		import heapq
		h = [(val, idx) for (idx, val) in enumerate(nums)]
		heapq.heapify(h)
		ans = 0
		for k in range(1, right + 1):
			(val, idx) = heapq.heappop(h)
			if k >= left:
				ans += val
			if idx + 1 < len(nums):
				heapq.heappush(h, (val + nums[idx + 1], idx + 1))
		return ans % 1000000007


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		subarray_sum = []
		for i in range(0, len(nums)):
			total_sum = 0
			for k in range(i, len(nums)):
				total_sum += nums[k]
				subarray_sum.append(total_sum)
		subarray_sum.sort()
		return sum(subarray_sum[left - 1:right]) % (10 ** 9 + 7)


class Solution:

	def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
		n = len(nums)
		heap = [(num, index) for (index, num) in enumerate(nums)]
		heapq.heapify(heap)
		count = 0
		range_sum = 0
		while heap:
			(num, index) = heapq.heappop(heap)
			count += 1
			if count >= left:
				range_sum += num
			if count == right:
				break
			if index < n - 1:
				heapq.heappush(heap, (num + nums[index + 1], index + 1))
		return range_sum % (10 ** 9 + 7)