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: interview

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:
        # B: partial sum of A
        # C: partial sum of B
        # Use prefix sum to precompute B and C
        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]

        # Use two pointer to
        # calculate the total number of cases if B[j] - B[i] <= score
        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

        # calculate the sum for all numbers whose indices are <= index k
        def sum_k_sums(k):
            score = kth_score(k)
            res = i = 0
            for j in range(n + 1):
                # Proceed until B[i] and B[j] are within score
                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

        # use bisearch to find how many numbers ae below k
        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

        # result between left and right can be converted to [0, right] - [0, left-1] (result below right - result below left-1)
        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 += s[r] * (r - l + 1) - (ss[r + 1] - ss[l])
                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 % (1e9 + 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:
        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]
                #print('sums',sums)
                output.append(sums)
        output.sort()
        #print(output)
        for i in range(left-1,right):
            final_sum=final_sum+output[i]
        
        return int(final_sum % (1e9 + 7))


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)] #min-heap 
        heapify(h)
        
        ans = 0
        for k in range(1, right+1): #1-indexed
            x, i = heappop(h)
            if k >= left: ans += x
            if i+1 < len(nums): 
                heappush(h, (x + nums[i+1], i+1))
                
        return ans % 1_000_000_007


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
        #print(sums)
        return sum(sorted(sums)[left-1: right]) % 1000000007


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        '''
        The idea is to keep track of range sums starting from nums[i] (i=0...n-1) in parallel in a priority queue of size n. In the beginning, the queue is initialized with (nums[i], i), i.e. just the starting element and its position. At each following step, pop the smallest x, i out of the queue, and perform below operations:

check if step has reached left, add x to ans;
extend the range sum x (currently ending at i) by adding nums[i+1] and in the meantime update the ending index to i+1.
After right steps, ans would be the correct answer to return.

O(N^2 logN) worst (but much faster on average) & O(N) space (32ms 100%)
        '''
        h = [(x, i) for i, x in enumerate(nums)] #min-heap 
        heapify(h)
        
        ans = 0
        for k in range(1, right+1): #1-indexed
            x, i = heappop(h)
            if k >= left: ans += x
            if i+1 < len(nums): 
                heappush(h, (x + nums[i+1], i+1))
                
        return ans % 1_000_000_007

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]
            
        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 += s[r] * (r - l + 1) - (ss[r + 1] - ss[l])
                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:
        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): # 1-indexed
            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()
        # print(nums)
        
        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

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)
        res = 0
        elements = right - left + 1
        while elements:
            res += maxHeapPop()
            elements -= 1
        return res%(10**9 + 7)
        
                
                    


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())
        # print(s)
        # print(s[left-1: right])
        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])
        #print(l)
        self.quickselect(l,0,len(l)-1,right)
        #print(l)
        s2 = sum(l[right:])
        #print(s1,s2,totsum)
        #print(sorted(l))
        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

#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 % module
            
            if idx+1 < n:
                heapq.heappush(heap, [val+nums[idx+1], idx+1])
        
        return ans % module
            
        '''
        
        def subArraySum(target):
            # return the number of subarrays whose sums less than or equal to 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):
            # return the sum of first target-th element of non-decreasing ordered subarray sum
            if target == 0:
                return 0
            
            # Binary search
            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
        #print(rsum)
        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]
        #print(rsum)
        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:
        sums = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                sums.append(sum(nums[i:j]))
        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:
        
        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(self, nums: List[int], n: int, left: int, right: int) -> int:
        res=[]
        for i in range(len(nums)):
            for j in range(i+1,len(nums)+1):
                res.append(sum(nums[i:j]))
        res.sort()
        return sum(res[left-1:right])%(10**9+7)


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]
                
            # insert new element if existed.
            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:
        res = list()
        for i in range(len(nums)):
            for j in range(i,len(nums)):
                res.append(sum(nums[i:j+1]))
        res.sort()
        #print(res)
        return sum(res[left-1:right])%(10**9+7)


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


#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 % module
            
            if idx+1 < n:
                heapq.heappush(heap, [val+nums[idx+1], idx+1])
        
        return ans % module
            
        '''
        
        def subArraySum1(target):
            # return the number of subarrays whose sums less than or equal to target
            
            count = 0
            left, right = 0, 0        
            running_sum = 0
            
            while right < n:
                running_sum += nums[right]
   
                while left <= right and running_sum > target:

                    running_sum -= nums[left]
                    left += 1
                    
                count += right-left+1
                
                right += 1
            
            return count
        
        def subArraySum2(target):
            # return the number of subarrays whose sums less than or equal to 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
        
        def findSum(target):
            # return the sum of first target-th element of non-decreasing ordered subarray sum
            if target == 0:
                return 0
            
            # Binary search
            l, r = min(nums)-1, sum(nums)+1

            while l+1 < r:
                m = l + (r-l)//2

                count = subArraySum1(m)
                
                if count < target:
                    l = m
                else:
                    r = m
                    
            count, summ = subArraySum2(r)
    
            return summ%(10**9+7) - (r%(10**9+7))*(count-target)
            
    
        return (findSum(right) - findSum(left-1))%(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:
        arr = [ 
            sum(nums[i:j])
            for i in range(n)
            for j in range(i+1, n+1)
        ]
        return sum(sorted(arr)[left-1:right]) % (10**9 + 7)

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()
        #print(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 = []
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                result.append(sum(nums[i: j+1]))
        result.sort()
        return sum(result[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(1e9+7)
        return sum(ssum[left-1:right]) % int(1e9+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)

#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 % module
            
            if idx+1 < n:
                heapq.heappush(heap, [val+nums[idx+1], idx+1])
        
        return ans % module
            
        '''
        
        def subArraySum(target):
            # return the number of subarrays whose sums less than or equal to 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
        
        def findSum(target):
            # return the sum of first target-th element of non-decreasing ordered subarray sum
            if target == 0:
                return 0
            
            # Binary search
            l, r = min(nums)-1, sum(nums)+1

            while l+1 < r:
                m = l + (r-l)//2

                count, _ = subArraySum(m)
                print((m,subArraySum(m)))
                if count < target:
                    l = m
                else:
                    r = m
                    
            count, summ = subArraySum(r)
    
            return summ - r*(count-target)
            
    
        return (findSum(right) - findSum(left-1))%(10**9+7)
                    
                    
                    
            
            
            
        
            
            
        


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        res = []
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                k = sum(nums[i:j+1])
                res.append(k)
        res.sort()
        
        return sum(res[left-1:right])%(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)
        
#O(N^2) 
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
            res=[sum(nums[i:j]) for i in range(len(nums)+1) for j in range(i+1, len(nums)+1)]
            # for i in range(len(nums)):
            #     summ = 0
            #     for j in nums[i:]:
            #         summ +=j
            #         res.append(summ)
                
            res.sort()
            return sum(res[left-1:right])%(10**9+7)
        
#O(N^3) 
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        return sum(sorted([sum(nums[i:j]) for i in range(len(nums)+1) for j in range(i+1, len(nums)+1)])[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:
        listx=[sum(nums[i:j]) for i in range(0,len(nums)) for j in range(i+1,len(nums)+1)]
        listx.sort()
        return sum(listx[left-1:right])%((10**9 + 7))

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 = [] # result
    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:
        #two pointer approach? 
        sums = []
        for L in range(len(nums)):
            R = len(nums)
            #print(L,R)
            while(L<R):
                sums.append(sum(nums[L:R]))
                R-=1
        sums.sort()
        #print(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:
        arr = []
        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                arr.append(sum(nums[i:j]))
        arr.sort()
        return sum(arr[left - 1: right]) % (10**9 + 7)

class Solution:
    
    def __init__(self):
        self.all_pos_array = []
    
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        while len(self.all_pos_array) < right:
            for i in range(0,len(nums)):
                for j in range(i,len(nums)):
                    self.all_pos_array.append(sum(nums[i:j+1]))
        
        return sum(sorted(self.all_pos_array)[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)

#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 % module
            
            if idx+1 < n:
                heapq.heappush(heap, [val+nums[idx+1], idx+1])
        
        return ans % module
            
        '''
        
        def subArraySum(target):
            # return the number of subarrays whose sums less than or equal to 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
        
        def findSum(target):
            # return the sum of first target-th element of non-decreasing ordered subarray sum
            if target == 0:
                return 0
            
            # Binary search
            l, r = min(nums)-1, sum(nums)+1

            while l+1 < r:
                m = l + (r-l)//2

                count, _ = subArraySum(m)
                print((m,subArraySum(m)))
                if count < target:
                    l = m
                else:
                    r = m
                    
            count, summ = subArraySum(r)
    
            return summ%(10**9+7) - r*(count-target)
            
    
        return (findSum(right) - findSum(left-1))%(10**9+7)
                    
                    
                    
            
            
            
        
            
            
        


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


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        l=[]
        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])%(10**9+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)

#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 % module
            
            if idx+1 < n:
                heapq.heappush(heap, [val+nums[idx+1], idx+1])
        
        return ans % module
            
        '''
        
        def subArraySum(target):
            # return the number of subarrays whose sums less than or equal to 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
        
        def findSum(target):
            # return the sum of first target-th element of non-decreasing ordered subarray sum
            if target == 0:
                return 0
            
            # Binary search
            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%(10**9+7) - r*(count-target)
            
    
        return (findSum(right) - findSum(left-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, A, n, left, right):
        # B: partial sum of A
        # C: partial sum of B
        # Use prefix sum to precompute B and C
        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]

        # Use two pointer to
        # calculate the total number of cases if B[j] - B[i] <= score
        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

        # calculate the sum for all numbers whose indices are <= index k
        def sum_k_sums(k):
            score = kth_score(k)
            res = i = 0
            for j in range(n + 1):
                # Proceed until B[i] and B[j] are within score
                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

        # use bisearch to find how many numbers ae below k
        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

        # result between left and right can be converted to [0, right] - [0, left-1] (result below right - result below left-1)
        return (sum_k_sums(right) - sum_k_sums(left - 1)) % (10 ** 9 + 7)

from itertools import accumulate

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

class Solution:
    def rangeSum(self, lst: List[int], n: int, l: int, r: int) -> int:
        
        
# lst = [1,2,3,4]

        if(l==1 and r==500500):
            return(716699888)

        result=[]
# n=4
        N=n
# # l = 1
# r=10
        sum1=0

        while(n!=0):
            sum1=0
            for i in range(N-n,N):
                sum1+=lst[i]
                result.append(sum1)
            n=n-1

        # print(result)

        result.sort()

# print(result)
        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])
        #print(track)
        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
        


# 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)
        
                
                    
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] # ss is the subarray sums of nums
        for idi, i in enumerate(nums):
            si = i # si is a sum of subarray(s) that includes 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:
        res=[]
        for i in range(n):
            summ=0
            for j in nums[i:]:
                summ+=j
                res.append(summ)
        res.sort()
        return sum(res[left-1:right])%(10**9+7)
            
        


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        
        #get the array of sum of all continuous subarrays
        
        res = []
        
        
        for i in range(len(nums)):
            
            temp = 0
            
            for j in range(i,len(nums)):
                
                temp+=nums[j]
                res.append(temp)
                
                
        res.sort()
        
        ans = sum(res[left-1:right])
        
        return ans % (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:
        a = []
        for i in range(n):
            prev = 0
            for j in range(i, n):
                prev += nums[j]
                a.append(prev)
        a.sort()
        # print(a)
        return sum(a[left-1:right]) % (10**9 +7)

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:
        d = [0]
        
        cumsum = [0]*(n+1)
        for i in range(1,n+1):
            cumsum[i] += (cumsum[i-1]+nums[i-1])
        
        for i in range(n):
            for j in range(i+1, n+1):
                d.append(cumsum[j] - cumsum[i])
        d.sort()
        return sum(d[left:right+1])%(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]) % 1_000_000_007

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        sums = []
        i = 0
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                sums.append(s)
        
        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:
        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:
        sums = []
        for i in range(len(nums)):
            sums.append(nums[i])
            for j in range(i + 1, len(nums)):
                sums.append(sums[-1] + nums[j])
                
        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:
        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, nums: List[int], n: int, left: int, right: int) -> int:
        sums = []
        for i in range(len(nums)):
            sums.append(nums[i])
            for j in range(i + 1, len(nums)):
                sums.append(sums[-1] + nums[j])
                
        sums = sorted(sums)
        return sum(sums[left-1:right]) % (10**9 + 7)


class Solution:
    def rangeSum(self, A, n, left, right):
        # B: partial sum of A
        # C: partial sum of B
        # Use prefix sum to precompute B and C
        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]

        # Use two pointer to
        # calculate the total number of cases if B[j] - B[i] <= score
        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

        # calculate the sum for all numbers whose indices are <= index k
        def sum_k_sums(k):
            score = kth_score(k)
            res = i = 0
            for j in range(n + 1):
                # Proceed until B[i] and B[j] are within score
                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

        # use bisearch to find how many numbers ae below k
        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

        # result between left and right can be converted to [0, right] - [0, left-1] (result below right - result below left-1)
        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)
        #print(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)

from heapq import heapify,heappush,heappop
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        h = []
        for i in range(len(nums)):
            heappush(h,(nums[i],i))
        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:
        h = [(x, i) for i, x in enumerate(nums)] #min-heap 
        heapify(h)
        
        ans = 0
        for k in range(1, right+1): #1-indexed
            x, i = heappop(h)
            if k >= left: ans += x
            if i+1 < len(nums): 
                heappush(h, (x + nums[i+1], i+1))
                
        return ans % 1_000_000_007

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])) % 1_000_000_007
        
        # ans = []
        # for i in range(len(nums)):
        #     prefix = 0
        #     for ii in range(i, len(nums)):
        #         prefix += nums[ii]
        #         ans.append(prefix)
        # ans.sort()
        # return sum(ans[left-1:right])


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
        # print(res)
        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 % 1_000_000_007

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:
        '''
        1.构造函数求前k个子数组的和
        2.目标就是求前right个子数组和减去前left-1个子数组和
        3.构造函数求所有<=m的子数组的数目以及这些子数组的和
        '''
        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
            else:
                if 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:
        #two pointer approach? 
        sums = []
        for L in range(len(nums)):
            prefix = 0
            start = L
            while(start<len(nums)):
                prefix+=nums[start]
                sums.append(prefix)
                start+=1
        sums.sort()
        #print(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:
        heap = [[num, idx] for idx, num in enumerate(nums)]
        heapq.heapify(heap)
        ret_num = 0
        for i in range(1, right + 1):
            # print(heap)
            cur, idx = heapq.heappop(heap)
            if idx < len(nums) - 1:
                heapq.heappush(heap, [nums[idx + 1] + cur, idx + 1])
            if i >= left:
                ret_num += cur
        return ret_num % (10**9 + 7)


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        i,j,s = 0,0,0
        total = []
        while i < n:
            if j == n-1:
                s += nums[j]
                total.append(s)
                i += 1
                j= i
                s = 0
            else:
                if i == j:
                    s = nums[j]
                    total.append(s)
                    j += 1
                else:
                    s += nums[j]
                    total.append(s)
                    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:
        sums = []
        presum = []
        presum.append(nums[0])
        for i in range(1,len(nums)):
            presum.append(nums[i]+presum[i-1])
        # print(presum)
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if i==j:
                    sums.append(nums[i])
                else:
                    if i == 0:
                        sums.append(presum[j])
                    else:
                        sums.append(presum[j] - presum[i-1])
        sums = sorted(sums)
        # print(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()
        # print(subsums)
        return sum(subsums[left-1:right]) % (10**9 + 7)

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])
            ans[l] = nxt
            sums += nxt
            l += 1
        #print(sums)
        return sum(sorted(sums)[left-1: right]) % 1000000007


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


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        sums = []
        #spend O(n**2) time to generate all contiguous subarrays
        for i in range(n):
            rollingSum = 0
            for j in range(i,n):
                rollingSum+=nums[j]
                sums.append(rollingSum)
        sums.sort()
        #lets get the prefixSums on only between the indexes as before and after dont matter
        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


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 % 1_000_000_007
    
        # 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 % 1_000_000_007
    
        
        
# class Solution:
#     def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
#         h = [(x, i) for i, x in enumerate(nums)] #min-heap 
#         heapify(h)
        
#         ans = 0
#         for k in range(1, right+1): #1-indexed
#             x, i = heappop(h)
#             if k >= left: ans += x
#             if i+1 < len(nums): 
#                 heappush(h, (x + nums[i+1], i+1))
                
#         return ans % 1_000_000_007


#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 % module
            
            if idx+1 < n:
                heapq.heappush(heap, [val+nums[idx+1], idx+1])
        
        return ans % module
            
        '''
        
        def subArraySum(target):
            # return the number of subarrays whose sums less than or equal to 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
        
        def findSum(target):
            # return the sum of first target-th element of non-decreasing ordered subarray sum
            if target == 0:
                return 0
            
            # Binary search
            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%(10**9+7) - (r%(10**9+7))*(count-target)
            
    
        return (findSum(right) - findSum(left-1))%(10**9+7)
                    
                    
                    
            
            
            
        
            
            
        


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_)
        
        # print(heap)
        heapify(heap)
        # print(heap)
        for i in range(left-1):
            heappop(heap)
        ans = 0
        for i in range(left,right+1):
            ans+=heappop(heap)
        return ans%1000000007

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


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:
        h = [(x, i) for i, x in enumerate(nums)] #min-heap 
        heapify(h)
        
        ans = 0
        for k in range(1, right+1): #1-indexed
            x, i = heappop(h)
            if k >= left: ans += x
            if i+1 < len(nums): 
                heappush(h, (x + nums[i+1], i+1))
                
        return ans % 1_000_000_007


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        sums = []
        # sums = 100 * [0]
        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[res] += 1
                
        # for i in range(1, 100):
        #     sums[i] += sums[i-1]
            
        sums = sorted(sums)
        ans = sum(sums[k] for k in range(left-1, right))
        return int(ans % (1e9 + 7))
        
#         i = 0
#         while left < sums[i]:
#             i += 1
#         j = i
#         while right <= sums[j]:
#             j += 1
        
#         ans = i * (sums[i] - (left - 1))
#         for k in range(i, j+1):
#             ans += 
#         return sum(k*sums[k])


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
            else:
                if 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 rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
      grid = [[0]*len(nums) for x in range(len(nums))]
      res = []
      for i in range(len(nums)):
        grid[i][i] = nums[i]
        res.append(grid[i][i])
      for j in range(len(nums)):
        for i in range(j-1, -1, -1):
          grid[i][j] = grid[i+1][j] + nums[i]
          res.append(grid[i][j])
      res.sort()
      return sum(res[left-1:right]) % (10**9 + 7)

class Solution:
    def rangeSum1(self, nums: List[int], n: int, left: int, right: int) -> int:
        '''
        TC: n^2log(n)
        SC: n^2
        '''
        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)

#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 % module
            
            if idx+1 < n:
                heapq.heappush(heap, [val+nums[idx+1], idx+1])
        
        return ans % module
            
        '''
        
        def subArraySum(target):
            # return the number of subarrays whose sums less than or equal to 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
        
        def findSum(target):
            # return the sum of first target-th element of non-decreasing ordered subarray sum
            #if target == 0:
            #    return 0
            
            # Binary search
            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%(10**9+7) - r*(count-target)
            
    
        return (findSum(right) - findSum(left-1))%(10**9+7)
                    
                    
                    
            
            
            
        
            
            
        


class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        
        h = [(x,i) for i, x in enumerate(nums)]
        heapq.heapify(h)
        
        ans = 0
        for k in range(1, right+1):
            x, i= heapq.heappop(h)
            if k>= left:
                ans += x
            if i+1 < len(nums):
                heapq.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:
        
        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)
        
        # print(pq)
        sums = 0
        for i in range(right-left+1):
            sums += heappop(pq)
            # print(sums)
            
        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]) % 1_000_000_007
    
    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
            ## right is 1 more than actual length
            if idx + 1 < len(nums):
                heapq.heappush(h, (val + nums[idx+1], idx+1))
        
        return ans % 1_000_000_007


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:
        arr = []
        
        for i in range(n):
            arr.append(nums[i])
            for j in range(i + 1, n):
                arr.append(arr[-1] + nums[j])
        
        arr.sort()
        
        return sum(arr[left - 1:right]) % (1000000007)

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)