Tí và Tèo đang cùng nhau học về cấu trúc dữ liệu và giải thuật. Để kiểm tra khả năng của Tèo, Tí đưa ra một thử thách với một mảng số nguyên \(a\) gồm \(n\) phần tử.

Tí sẽ đưa ra \(q\) câu hỏi, mỗi câu hỏi là một cặp số \((l, r)\). Với mỗi câu hỏi, Tèo cần đếm xem trong mảng \(a\) có bao nhiêu phần tử có giá trị nằm trong đoạn \([l, r]\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) (\(l \le r, |l|, |r| \le 10^9\)).

Output

• Với mỗi câu hỏi, in ra một số nguyên duy nhất trên một dòng là số lượng phần tử trong mảng \(a\) có giá trị thuộc đoạn \([l, r]\).

Example

5 3
1 3 5 7 9
2 6
1 9
10 15

2
5
0

Constraints

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \le 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.