← 返回 ramp 的题目列表Maximum Number of Consecutive Items Purchasable From Each Start Index
类型：online_judge
Problem Statement
You are given an array prices, where prices[i] is the price of the i-th item.
You are also given multiple queries. Each query is a pair [start, fund]:
start means you must start buying from prices[start];
fund is the amount of money available;
you may only buy items consecutively in array order, i.e. prices[start], prices[start + 1], ...;
you cannot skip any item;
the total cost of purchased items must not exceed fund.
For each query, return the maximum number of consecutive items you can buy starting from start.
If prices[start] > fund, the answer is 0.
Assume start is 0-indexed.
Input Format
n
prices[0] prices[1] ... prices[n-1]
q
start_1 fund_1
start_2 fund_2
...
start_q fund_q
Output Format
Print q lines. The i-th line should contain the answer for the i-th query.
Constraints
1 <= n <= 2 * 10^5
1 <= q <= 2 * 10^5
1 <= prices[i] <= 10^9
0 <= start < n
0 <= fund <= 10^18
Example
Input
5
2 3 5 4 1
3
0 10
1 8
3 3
Output
3
2
0
Explanation
Query [0, 10]: starting from price 2, we can buy 2 + 3 + 5 = 10, so the answer is 3.
Query [1, 8]: starting from price 3, we can buy 3 + 5 = 8, so the answer is 2.
Query [3, 3]: the first required item costs 4, which exceeds the fund, so the answer is 0.
Example
Input
5
2 3 5 4 1
3
0 10
1 8
3 3
Output
3
2
0