952. Range Minimum Query (Segment Tree)

Given an integer array and a list of range queries [l, r], return the minimum element in each range (inclusive), using a segment tree (or sparse table). Return the answers as an array in order. The input is JSON {nums, queries}.

Input: JSON {nums, queries}.

Output: Array — the minimum for each query.

Examples

Input: {"nums":[5,2,8,1,9,3],"queries":[[0,2],[1,4],[3,5]]}
Output: [2,1,1]
Explanation: Range minimums.

Input: {"nums":[7],"queries":[[0,0]]}
Output: [7]
Explanation: Single element.

Input: {"nums":[3,1,4,1,5],"queries":[[0,4],[2,3]]}
Output: [1,1]
Explanation: Two ranges.

Constraints

• 1<=n<=10^5
• 1<=queries<=10^5
• 0<=l<=r<n

Asked by