Bờm sắp xếp ~N~ (~1≤N≤10^5~) viên bi tại nhiều điểm khác nhau dọc theo trục số Ox. Để đảm bảo chúng được đặt cách nhau một cách hợp lý, vui lòng giúp anh ấy trả lời ~Q~ (~1≤Q≤10^5~) câu hỏi, mỗi câu hỏi về số lượng viên bi trong một khoảng cụ thể dọc trên trục số.

Dữ liệu:

Cho từ tệp MARBLES.INP

-Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~;

-Dòng thứ hai chứa các giá trị ~x_1,x_2,..,x_n~ (~0≤x_i≤10^9~) là tọa độ của các viên bi;

-~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l,r~ (~0≤l≤r≤10^9~) thể hiện 1 truy vấn – đếm số lượng bi tại tọa độ ~l~ đến ~r~.

Kết quả:

Ghi ra tệp MARBLES.OUT

Gồm ~Q~ dòng, mỗi dòng là kết quả của 1 truy vấn.

Ví dụ:

Input

4 6

3 2 7 5

2 3

2 4

2 5

2 7

4 6

8 10

Output

2

2

3

4

1

0

Giải thích ví dụ:

Truy vấn 1: số bi trong đoạn tọa độ [2, 3] là 2

Truy vấn 2: số bi trong đoạn tạo độ [2, 4] là 2

Truy vấn 3: số bi trong đoạn tọa độ [2, 5] là 3

Truy vấn 4: số bi trong đoạn tọa độ [2, 7] là 4

Truy vấn 5: số bi trong đoạn tọa độ [4, 6] là 1

Truy vấn 6: số bi trong đoạn tọa độ [8, 10] là 0

Giới hạn

• 60% số test đầu tiên: ~N,Q≤10^3~;
• 40% số test cuối cùng không có ràng buộc gì thêm.