Bindu 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 Bindu 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 HTM Airway - dưới sự lãnh đạo của chủ tịch HTM và phó chủ tịch 4uckd3v. Dù vậy, Bindu 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_1, a_2, a_3, ..., a_n\) rồi yêu cầu 4uckd3v phải trả lời \(Q\) câu hỏi. Ở mỗi câu hỏi, Bindu đưa ra hai vị trí \(L\) và \(R\) \((1 \leq L < R \leq n)\) rồi yêu cầu 4uckd3v đếm xem có bao nhiêu cặp vị trí \((i, j)\) sao cho \(\left|a_i-a_j\right| > 1\) và \(L \leq i < j \leq R\). 4uckd3v nhanh chóng giải đáp được một số câu hỏi đầu của Bindu nhưng vì số câu hỏi quá lớn nên 4uckd3v 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 4uckd3v giải đáp tất cả \(Q\) câu hỏi để chiêu mộ nhân tài Bindu nhé!

Input:

• Dòng đầu chứa số nguyên dương \(n \leq 50,000\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1, a_2,...,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 \leq 50,000\) là số lượng câu hỏi dành cho 4uckd3v.
• \(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.

Output:

• 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 Bindu.

Ví dụ

Sample input 01

6
1 2 3 7 8 9
2
2 3
3 5

Sample output 01

0
2