Welcome Back Contest: 2025 Problem 2

Every student in the school board has their own unique student ID based on when they joined the school board. Mr. Quinn wonders how many students in his class of ~N~ students joined during certain periods of time. More specifically, he asks ~Q~ questions of the form

How many students in my class have student IDs between ~u~ and ~v~ inclusive?

Since Mr. Quinn is too busy marking, he needs your help to answer these questions!

Input Specification

The first line contains the integers ~N~ and ~Q~, separated by a single space.

The next line contains ~N~ spaced integers ~a_1, a_2, ... a_N~, representing the unique IDs of the students in the class.

The next ~Q~ lines contain two spaced integers, ~u~ and ~v \, (u \le v)~, representing a question to be answered.

Output Specification

For each question, output the answer on its own line.

Subtasks

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

~1 \le a_i,u,v \le 10^9~

Subtask 1 [20%]

~1 \le N, Q \le 100~

~1 \le a_i,u,v \le 100~

Subtask 2 [30%]

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

~1 \le a_i,u,v \le 10^6~

Subtask 3 [50%]

No additional constraints

Sample Input 1

5 3
2 5 1 8 6
1 3
2 7
6 6

Output for Sample Input 1

2
3
1

Explanation of Output for Sample Input 1

For the first question, there are ~2~ student IDs between ~1~ and ~3~ inclusive (~2~ and ~1~).

For the second question, there are ~3~ student IDs between ~2~ and ~7~ inclusive (~2~, ~5~ and ~6~).

For the third question, there are ~2~ student IDs between ~6~ and ~6~ inclusive (just ~6~).

Sample Input 2

7 3
46 23 91 15 67 24 50
1 100
16 22
20 50

Output for Sample Input 2

7
0
4