Requests in a window: hints, no solution

An API gateway writes the arrival time of every request, in milliseconds since midnight, to a log that is already sorted from earliest to latest. Several requests can share the same millisecond.

An engineer asks how busy the service was in many windows. Window j runs from starts[j] to ends[j]: return how many logged requests arrived at a time t with starts[j] <= t <= ends[j]. Both ends count. If a start is greater than its end, that window is empty and its answer is 0. Return the answers in window order.

The log holds a great many entries and is queried again and again, so each answer should come from two searches rather than a pass over the whole log.

Examples

Input

timestamps = [1, 3, 3, 5, 9, 12], starts = [3, 10], ends = [9, 11]

Output

[4, 0]

Note

The first window holds 3, 3, 5 and 9; nothing arrived between 10 and 11.

Input

timestamps = [2, 2, 2, 2], starts = [2, 5], ends = [2, 1]

Output

[4, 0]

Note

A one-instant window counts every request at it; a backwards window is empty.

Constraints

• 0 <= timestamps.length <= 100000
• timestamps is sorted ascending and may contain duplicates
• 0 <= timestamps[i], starts[j], ends[j] <= 100000000
• starts and ends have equal length, 0 to 2000

Hint 1: a nudge

A window has a left edge and a right edge. Can you count the requests before each edge separately, and what would the difference tell you?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing