Đếm phần tử trong đoạn

Cho mảng \(A\) gồm \(N\) số nguyên và \(T\) truy vấn. Mỗi truy vấn gồm hai số \(L\) và \(R\), yêu cầu đếm xem có bao nhiêu phần tử của mảng \(A\) thuộc đoạn \([L, R]\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(T\) (\(1 \le N, T \le 10^5\)).

• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\) (\(1 \le A_i \le 10^5\)).

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le 10^5\)).

Output

Với mỗi truy vấn, in ra một dòng chứa số lượng phần tử của mảng \(A\) nằm trong đoạn \([L, R]\).

Example

Input:

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

Output:

4
3
1