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 ~N~ integers and ~Q~ subarray queries, compute the range of each subarray.

Constraints

~1 \le N \le 5 \cdot 10^4~

~1 \le Q \le 2 \cdot 10^5~

~1 \le a_i \le b_i \le N~

~a_i, b_i \in \mathbb{C}~

The elements of the array are positive integers up to a million.

Input Specification

The first line contains two integers, ~N~ and ~Q~.

Each of the next ~N~ lines contains a single integer. These ~N~ lines constitute the values of the array in order.

Each of the next ~Q~ lines contains two integers, ~a_i~ and ~b_i~, indicating a 1-indexed query.

Output Specification

For each query, print on a separate line the range of the subarray with leftmost index ~a_i~ and rightmost index ~b_i~.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0