K. Kronos
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the year $$$2087$$$, humanity developed temporal communication technology, allowing messages to be sent to the past. You work at the Temporal Monitoring Center and need to process queries about these messages from the future.

You receive $$$N$$$ messages from the future, each with a timestamp $$$t_i$$$ indicating when the message was originally sent (in the future). Your system needs to respond to $$$Q$$$ queries, where each query asks: "How many messages were sent in the time interval [L, R]?"

Input

First line: two integers $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 2 \cdot 10^5)$$$

Second line: $$$N$$$ integers $$$t_i$$$ representing the timestamps of the messages $$$(1 \leq t_i \leq 10^9)$$$

The next $$$Q$$$ lines: two integers $$$L$$$ and $$$R$$$ for each query $$$(1 \leq L \leq R \leq 10^9)$$$

Output

For each query, print the number of messages received in the closed interval $$$[L, R]$$$.

Examples
Input
5 3
10 1 10 7 5
1 5
6 10
2 4
Output
2
3
0
Input
3 3
10 15 20
1 5
10 10
15 25
Output
0
1
2
Input
6 5
600 500 400 300 200 100
100 100
50 350
1 1000000000
401 600
700 800
Output
1
3
6
2
0