Counting Students in Magical Ability Ranges

In this problem, you are given a list of students where each student has a magical ability represented by a positive integer. You are also given several queries, each specifying an inclusive range \( [l, r] \) of magical abilities. Your task is to count the number of students whose magical abilities fall within each provided range.

It is guaranteed that the magical abilities of all students are within the range from 1 to n (where n is the number of students). Use efficient methods such as prefix sums to answer the queries promptly.

The input is read from standard input (stdin) and the output should be written to standard output (stdout).

inputFormat

The first line contains two integers n and m, representing the number of students and the number of queries respectively. The second line contains n integers, each representing a student's magical ability. The following m lines each contain two integers l and r representing the inclusive range of abilities for a query.

outputFormat

For each query, output a single integer on a new line—the number of students whose magical abilities are within the inclusive range [l, r].## sample

5 3
1 2 3 4 5
1 3
2 4
3 5

3
3
3