zipdang04 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 zipdang04 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, zipdang04 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 ami phải trả lời \(Q\) câu hỏi. Ở mỗi câu hỏi, zipdang04 đưa ra hai vị trí \(L\) và \(R\) \((1 \leq L < R \leq n)\) rồi yêu cầu ami đế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\). ami nhanh chóng giải đáp được một số câu hỏi đầu của zipdang04 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 zipdang04 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 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.

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 zipdang04.

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

0
2

Cho một xâu \(S\) chỉ gồm các chữ cái in thường. Cách mô tả rút gọn của xâu \(S\) như sau:

• Chọn ra một xâu \(X\) ngắn nhất có thể và một số nguyên dương \(K\), sao cho khi viết xâu \(X\) lặp lại \(K\) lần thì ta thu được xâu \(S\)
• Ghép \(K\) và \(X\), ta thu được xâu rút gọn của \(S\).

Ví dụ:

• Xâu rút gọn của “abababab” là “4ab”
• Xâu rút gọn của “aaa” là “3a”
• Xâu rút gọn của “abac” là “1abac”

Input

• Gồm một dòng duy nhất chứa xâu \(S\) có độ dài không quá \(1000\).

Output

• In ra xâu rút gọn của xâu \(S\).

Example

abababab 

4ab

aaa 

3a

abac 

1abac