Roger is training for CCO and has decided to practice implementing segment trees. He decides to solve a classic problem that is solvable with segment trees.
Given an array with integers and subarray queries, compute the range of each subarray.
The elements of the array are positive integers up to a million.
The first line contains two integers, and .
Each of the next lines contains a single integer. These lines constitute the values of the array in order.
Each of the next lines contains two integers, and , indicating a 1-indexed query.
For each query, print on a separate line the range of the subarray with leftmost index and rightmost index .
6 3 1 7 3 4 2 5 1 5 4 6 2 2
6 3 0