Max purchases from a sorted price row

A market hall has n stalls in a row, numbered 1..n. Stall i sells a single kind of item at price prices[i-1], and the prices are non-decreasing from left to right. A shopper may buy at most one item per stall.

You are given q queries as two arrays of length q, pos and amount. For query j, the shopper starts at stall pos[j] and may visit only stalls pos[j], pos[j]+1, ..., n. Return an array where entry j is the maximum number of items the shopper can buy in query j with total cost at most amount[j].

Implement:

def max_items(prices: list[int], pos: list[int], amount: list[int]) -> list[int]: ...

Constraints

• 1 <= n, q <= 10^5
• 0 <= prices[i] <= 10^9, and prices[i] <= prices[i+1]
• 1 <= pos[j] <= n
• 0 <= amount[j] <= 10^14

Example 1

prices = [2, 3, 5, 8]
pos    = [1, 2, 4]
amount = [10, 7, 7]
output = [3, 1, 0]

From stall 1 with 10: buy 2 + 3 + 5 = 10, so 3 items. From stall 2 with 7: 3 fits, 3 + 5 does not, so 1. From stall 4 with 7: the only item costs 8, so 0.

Example 2

prices = [1, 1, 1]
pos    = [1, 3]
amount = [100, 0]
output = [3, 0]

A brute-force walk per query is O(n * q). Aim for better.