← 返回 doordash 的题目列表Segment Tree Problem
类型：online_judge
doordash
Implement a segment tree for range minimum queries. Given an integer array and several queries, each query requests to return the minimum value in a specified subarray.
Input Format:
The first line contains two integers n and q (1 ≤ n, q ≤ 100,000), representing the length of the array and the number of queries.
The second line contains n integers representing the initial values of the array.
The next q lines, each contains two integers l and r (1 ≤ l ≤ r ≤ n), representing the range of the query.
Output Format:
For each query, output the minimum value in the specified range.
Sample Input:
5 3
1 2 3 4 5
1 3
2 5
1 5
Sample Output:
1
2
1
Example
Input
5 3
1 2 3 4 5
1 3
2 5
1 5