Amplitude's latest feature request is for frequency queries. More specifically, a customer has ~N~ different users. User ~i~ has performed a certain event ~p_i~ times. This customer wishes to know how many customers have performed the event between ~L~ and ~R~ times. Your job is to implement support for frequency queries!

Constraints

~1 \le N, Q \le 10^6~

~0 \le p_i \le 10^6~

~0 \le L \le R \le 10^6~

Subtask 1 [1 point]

~1 \le N, Q \le 10^3~

~0 \le p_i \le 10^3~

~R \le 10^3~

Subtask 2 [1 point]

No additional constraints.

Input Specification

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

The next line contains ~N~ nonnegative integers. The ~i~th integer, ~p_i~, is the number of times user ~i~ performed the event.

Each of the next ~Q~ lines contains two integers, ~L~ and ~R~. This represents a single frequency query, and the customer wants to know how many users performed the event between ~L~ and ~R~ times, inclusive.

Output Specification

Output ~Q~ lines. On the ~i~th line, output the answer to the ~i~th frequency query.

Sample Input

3 10
0 1 3
0 0
0 1
0 2
0 3
1 1
1 2
1 3
2 2
2 3
3 3

Sample Output

1
2
2
3
1
1
2
0
1
1

Sample Explanation

There are three users. One has performed the event zero times, one has performed the event once, and one has performed the event three times. Over all the frequency queries, the only one that returns zero is the one asking for how many users have performed the event exactly twice.