Roger is training for CCO and has decided to practice implementing rage trees. He decides to solve a classic problem that is solvable with rage trees.
Given an array with integers and
subarray queries, compute the range of each subarray.
Constraints
The elements of the array are positive integers up to a million.
Input Specification
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.
Output Specification
For each query, print on a separate line the range of the subarray with leftmost index and rightmost
index
.
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
Comments