Farmer John vừa sắp xếp \(N\) kiện cỏ khô (\(1 \leq N \leq 100\,000\)) tại nhiều vị trí khác nhau dọc theo con đường chạy xuyên qua trang trại, được xem như một trục một chiều. Để đảm bảo chúng được đặt cách nhau hợp lý, hãy giúp ông trả lời \(Q\) truy vấn (\(1 \leq Q \leq 100\,000\)), mỗi truy vấn hỏi số kiện cỏ khô nằm trong một đoạn cụ thể trên con đường.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\).

Dòng tiếp theo chứa \(N\) số nguyên phân biệt, mỗi số nằm trong khoảng \(0 \ldots 1\,000\,000\,000\), cho biết có một kiện cỏ khô tại mỗi vị trí tương ứng.

Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên \(A\) và \(B\) (\(0 \leq A \leq B \leq 1\,000\,000\,000\)), biểu thị một truy vấn về số kiện cỏ khô nằm giữa \(A\) và \(B\), tính cả hai đầu mút.

Dữ liệu ra

In \(Q\) dòng. Với mỗi truy vấn, in số kiện cỏ khô trong đoạn tương ứng.

Ví dụ

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

2
2
3
4
1
0

Nguồn

USACO 2016 December Contest, Silver — Counting Haybales. Tác giả đề: Nick Wu.

https://usaco.org/index.php?page=viewproblem2&cpid=666