Bình có một BST được tạo từ \(N\) số nguyên dương phân biệt. Bình muốn đếm số nút có giá trị nằm trong đoạn \([L, R]\).

Hãy giúp Bình viết chương trình đếm số nút trong BST có giá trị thuộc đoạn \([L, R]\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^3\)).
• Dòng thứ hai chứa \(N\) số nguyên dương phân biệt \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lượng nút có giá trị trong đoạn \([L, R]\).

Ví dụ

Input:

7 3
5 3 7 2 4 6 8
3 5
4 7
10 20

Output:

3
4
0

Giải thích:

• Đoạn \([3, 5]\) gồm các giá trị \(3, 4, 5\): 3 nút.
• Đoạn \([4, 7]\) gồm các giá trị \(4, 5, 6, 7\): 4 nút.
• Đoạn \([10, 20]\): 0 nút.