537. Minimum Interval to Include Each Query

Given a set of intervals [left, right] and a list of queries, for each query return the size (right - left + 1) of the smallest interval that contains the query (left <= query <= right), or -1 if no interval contains it. The input is JSON {intervals, queries}. Return an array of answers in the original query order.

Input: JSON {intervals, queries}.

Output: Array — minimum interval size per query (-1 if none).

Examples

Input: {"intervals":[[1,4],[2,4],[3,6],[4,4]],"queries":[2,3,4,5]}
Output: [3,3,1,4]
Explanation: Smallest containing interval size per query.

Input: {"intervals":[[1,1]],"queries":[1,2]}
Output: [1,-1]
Explanation: Only the first query is contained.

Constraints

• 1<=intervals,queries<=10^5
• 1<=left<=right<=10^7

Asked by