All problems

What Is Printing Now

Medium · binary search

A print shop has a queue of jobs. Job i takes durations[i] whole minutes, and the printer runs the jobs back to back in the order given, with no gaps, starting at minute 0. So the first job prints during minutes 0 to durations[0] - 1, the second starts the minute after the first one ends, and so on.

Customers phone in with a list of minutes queries and ask: "which job is printing at that minute?"

Return a list with one number per query, in the same order: the position (counting from 0) of the job that is printing at that minute, or -1 if every job has already finished by then.

Examples

Example 1

Input: durations = [3, 1, 2], queries = [0, 2, 3, 4, 5, 6]

Output: [0, 0, 1, 2, 2, -1]

Job 0 prints in minutes 0 to 2, job 1 in minute 3, job 2 in minutes 4 and 5. Nothing is printing at minute 6.

Example 2

Input: durations = [5], queries = [4, 5]

Output: [0, -1]

Constraints