zipdang vừa tốt nghiệp thủ khoa Học viện Hàng không ở tuổi 15. Các hãng hàng không lớn đã lũ lượt đưa ra những bổng lộc hấp dẫn để thu hút phi công zipdang về với công ty của mình. Tuy nhiên, cậu chỉ dành sự quan tâm của mình cho duy nhất hãng LMH Airway - dưới sự lãnh đạo của chủ tịch LMH và phó chủ tịch Ami. Dù vậy, zipdang vẫn yêu cầu ngài phó chủ tịch phải vượt qua được một thách thức của mình để hoàn toàn làm cậu tâm phục khẩu phục quy thuận công ty.

Cậu viết ra một dãy số nguyên dương a₁, a₂, a₃...a_n rồi yêu cầu Ami phải trả lời Q câu hỏi. Ở mỗi câu hỏi, zipdang đưa ra hai vị trí L và R (1 <= L < R <= n) rồi yêu cầu Ami đếm xem có bao nhiêu cặp vị trí (i, j) sao cho |a_i-a_j| > 1 và L <= i < j <= R. Ami nhanh chóng giải đáp được một số câu hỏi đầu của zipdang nhưng vì số câu hỏi quá lớn nên Ami dần lâm vào tình trạng hoa mắt chóng mặt với mớ dữ liệu phức tạp này. Bạn hãy giúp Ami giải đáp tất cả Q câu hỏi để chiêu mộ nhân tài zipdang nhé!

Dữ liệu vào:

-Dòng đầu chứa số nguyên dương n <= 50,000.

-Dòng tiếp theo chứa n số nguyên dương a₁, a₂,...a_n. Các số đều không vượt quá 10,000.

-Dòng tiếp theo chứa số nguyên dương Q <= 50,000 là số lượng câu hỏi dành cho Ami.

-Q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương L và R biểu thị câu hỏi tương ứng.

Kết quả: Gồm Q dòng, mỗi dòng chứa một số nguyên là đáp số cho câu hỏi tương ứng của zipdang.