Charlotte can now write many Arabic numerals, so her teacher gave her an advanced assignment.
First, given an array A of N numbers and Q queries.
Each query consists of two numbers L and R. For each query, Charlotte needs to answer how many i satisfy L ≤ A[i] ≤ R in the given array A (where i is integer and 1 ≤ i ≤ N).
Please help Charlotte complete her homework.
The first line contains two numbers N, Q (1 ≤ N ≤ 2 × 105, 1 ≤ Q ≤ 2 × 105).
The second line contains N numbers representing A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ 108).
The next Q lines each contain two numbers L and R (guaranteed that 1 ≤ L ≤ R ≤ 108).
Output Q lines, each representing the answer to the corresponding query.
Please add a newline('\n') at the end of each line.