Answer range-sum queries on a book after pages are reordered, using efficient preprocessing and search.
Problem Summary
You are given a book with pages, each page having a positive thickness/value. You must process queries. For each query, you are given a target value , and you need to determine the position of the page where the cumulative thickness first reaches at least .
The key difficulty is that the pages are not considered in their original order directly; instead, you should think in terms of prefix sums over the book layout and locate the first page whose prefix sum covers the requested value.
Task
For every query, report the page index that contains the -th unit in the ordered sequence of all pages.
Input Format
- The first line contains an integer .
- The second line contains positive integers describing the page thicknesses/values.
- The third line contains an integer .
- Each of the next lines contains one integer .
Output Format
For each query, output the 1-based index of the page that contains the requested position .
Constraints
- All page values are positive integers
- Query values are within the total sum of all page values
Example 1
Input
5 2 7 3 4 6 3 1 5 14
Output
1 2 4
Explanation
Prefix sums are [2, 9, 12, 16, 22].
- x=1 lies on page 1
- x=5 lies on page 2
- x=14 lies on page 4
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.