You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer weirdly values the colored balls. Each colored ball's value is the number of balls of that color&nbsp;you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, inventory, where inventory[i] represents the number of balls of the ith color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.


Example 2:

Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.


&nbsp;
Constraints:


	1 &lt;= inventory.length &lt;= 105
	1 &lt;= inventory[i] &lt;= 109
	1 &lt;= orders &lt;= min(sum(inventory[i]), 109)


class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        inventory.sort(reverse=True) 
        inventory += [0]
        res = 0
        k = 1
        
        for i in range(len(inventory)-1): 
            if inventory[i] > inventory[i+1]: 
                if k*(inventory[i]-inventory[i+1]) < orders:
                    diff = inventory[i]-inventory[i+1]
                    res += k*(inventory[i]+inventory[i+1]+1)*(diff)//2
                    orders -= k*diff
                else: 
                    q, r = divmod(orders, k)
                    res += k*(inventory[i]+(inventory[i]-q+1))*q//2
                    res += r*(inventory[i]-q)
                    return res%(10**9+7)
            k += 1
class Solution {
    private long mod = 1000000007L;
    public int maxProfit(int[] inventory, int orders) {
		// we use pq to find the most balls
        PriorityQueue<Long> pq = new PriorityQueue<>((x, y) -> Long.compare(y, x));
        pq.offer(0L);
		
        // we use map to count the balls
        Map<Long, Long> map = new HashMap<>();
        map.put(0L, 0L);
        
        for (int j : inventory) {
            long i = (long)j;
            if (map.containsKey(i)) {
                map.put(i, map.get(i) + 1);
            }
            else {
                pq.offer(i);
                map.put(i, 1L);
            }
        }
        
        long res = 0;
        while (orders > 0) {
            long ball = pq.poll(), nextBall = pq.peek();
            long times = map.get(ball);
            long diff = Math.min(ball - nextBall, orders / times);
            if (diff == 0) {
                res = (res + orders * ball) % mod;
                break;
            }
            long sum = (ball * 2 + 1 - diff) * diff / 2 * times;
            res = (res + sum) % mod;
            orders -= diff * times;
            if (!map.containsKey(ball - diff)) {
                map.put(ball - diff, map.get(ball));
                pq.offer(ball - diff);
            }
            else {
                map.put(ball - diff, map.get(ball - diff) + map.get(ball));
            }
            map.remove(ball);
        }
        return (int) res;
    }
}
#define ll long long
const int MOD = 1e9+7; 

class Solution {
public:
    
    ll summation(ll n) {
        return (n*(n+1)/2);
    }
    
    int maxProfit(vector<int>& inventory, int orders) {
        ll n = inventory.size(), i = 0, ans = 0;
        inventory.push_back(0);
        sort(inventory.rbegin(), inventory.rend());
        while(orders and i < n) {
            if(inventory[i] != inventory[i+1]) {
                ll width = i+1, h = inventory[i] - inventory[i+1];
                ll available = width * h, gain = 0;
                if(available <= orders) {
                    orders -= available;
					// from each of the first i+1 inventories, we gain (inventory[i+1] + 1) + ... + inventory[i] value
                    gain = (width * (summation(inventory[i]) - summation(inventory[i+1]))) % MOD; 
                } else {
                    ll q = orders / width, r = orders % width;
					// q balls picked from each of the first i+1 inventories
                    gain = (width * (summation(inventory[i]) - summation(inventory[i]-q))) % MOD;
					// 1 ball picked from r inventories providing value (inventory[i]-q)
                    gain = (gain + r*(inventory[i]-q)) % MOD;
                    orders = 0;
                }
                
                ans = (ans + gain) % MOD; 
            }
            
            i++;
        }
        
        return ans;
    }
};
var maxProfit = function(A, k) {
    //rangeSum Formula
    let rangesum=(i,j)=>{
        i=BigInt(i),j=BigInt(j)
        return ((j*((j+1n))/2n)-(i*(i+1n)/2n))
    }
    A.unshift(0) //prepend the sentinel 0 
    A.sort((a,b)=>a-b)
    let n=A.length,result=0n,mod=BigInt(1e9+7),i=n-1
    // can use all current levels
    while((k>=(n-i)*(A[i]-A[i-1]))&&i>0){
        if(A[i]!=A[i-1])
            result=(result+(rangesum(A[i-1],A[i])*BigInt(n-i)))%mod,
            k-=(n-i)*(A[i]-A[i-1])
        i--
    }
    //can use some of the current levels
    if(k>0&&k>=n-i){
        let levels=Math.floor(k/(n-i)) //the levels i can use 
        result=(result+(BigInt(n-i)*rangesum(A[i]-levels,A[i])))%mod
        k-=levels*(n-i)
        A[i]-=levels
    }
    // can use some of the items OF the first level
    if(k>0&&k<n-i)
        result=(result+BigInt(k)*BigInt(A[i]))%mod
    return Number(result)
};
Sell Diminishing-Valued Colored Balls