C. CNTSEQ - Số lượng dãy con

Cho dãy số nguyên . Một dãy con là dãy được lập từ dãy đã cho bằng cách giữ lại một đoạn liên tiếp các số cạnh nhau. Giá trị của một dãy được tính bằng giá trị của phần tử lớn nhất trong dãy.

Viết chương trình xác định với mỗi truy vấn dạng hãy đếm xem có bao nhiêu dãy con của dãy đã cho có giá trị nằm trong đoạn ?

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ;
• Dòng thứ hai chứa số nguyên dương mỗi số cách nhau bởi ít nhất một dấu cách;
• Dòng thứ ba ghi số nguyên dương - số lượng truy vấn;
• dòng cuối cùng, mỗi dòng chứa hai số nguyên - mô tả một truy vấn đếm xem có bao nhiêu dãy con có giá trị nằm trong ?

Dữ liệu ra:

• Gồm dòng, mỗi dòng ghi kết quả một truy vấn theo thứ tự xuất hiện trong dữ liệu vào.

Ví dụ:

Dữ liệu vào:

3
1 2 3
3
1 2
2 3
3 3

Dữ liệu ra:

3
5
3

Ràng buộc:

• Có số điểm ứng với ;
• Có số điểm còn lại ứng với .