Problem

Alice is shopping at Ozone Galleria Mall, where each cubicle sells products at a fixed price. The cubicles are arranged so that prices are in non-decreasing order from left to right.

There is an array of n integers, prices, where prices[i] is the price at the i-th cubicle, and q queries to process. For each query, you are given:

• pos: Alex's initial position
• amount: the amount of money Alex has

Alex visits each cubicle from position pos to n and can purchase a maximum of one product from each cubicle visited. The goal is to determine the maximum number of products Alex can buy without exceeding the available amount.

Input

• An array of integers representing the prices of products in each cubicle
• A list of queries, where each query contains Alex's initial position and the amount of money Alex has

Output

• The maximum number of products Alex can buy for each query

Example

• n = 5
• prices = [3, 4, 5, 5, 7]
• q = 3
• queries = [[2, 10], [1, 24], [5, 5]]

Queries:

1. pos = 2, amount = 10: Alex visits cubicles 2 through 5 and can buy at most 2 products. Alex can either buy from:
   • Cubicles 2 and 3: 4 + 5 = 9 (<= 10)
   • Cubicles 2 and 4: 4 + 5 = 9 (<= 10)
   • Cubicles 3 and 4: 5 + 5 = 10 (<= 10) The answer is 2.
2. pos = 1, amount = 24: Alex visits all cubicles and can buy from all of them since the total cost is 3 + 4 + 5 + 5 + 7 = 24 (<= 24). The answer is 5.
3. pos = 5, amount = 5: Alex can only visit cubicle 5 but cannot make any purchase since the price (7) exceeds the available amount (5). The answer is 0.

Hint : Prefix sums and binary search