Farmer John vừa đặt $N$ kiện cỏ khô ($1 \leq N \leq 100,000$) của mình tại nhiều vị trí trên con đường được xem là một trục một chiều chạy qua trang trại. Để đảm bảo chúng được đặt cách nhau phù hợp, 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ô trong một đoạn cụ thể trên đườ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ố thuộc khoảng $0 \ldots 1,000,000,000$, cho biết có một kiện cỏ khô tại mỗi vị trí đó.

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 diễn truy vấn về số kiện cỏ khô từ $A$ đến $B$, kể cả hai đầu mút.

Dữ liệu ra

Bạn cần 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ụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
2
3
4
1
0

Tác giả bài toán: Nick Wu