Cho dãy số nguyên ~a_1~, ~a_2~, …, ~a_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.

Yêu cầu: Với mỗi truy vấn dạng ~L, R~ hãy đếm xem có bao nhiêu dãy con của dãy đã cho có giá trị nằm trong đoạn ~[L, R]~.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~n~
• Dòng thứ hai chứa n số nguyên dương ~a_1~, ~a_2~, …, ~a_n~
• Dòng thứ ba ghi số nguyên dương ~m~ là số lượng truy vấn
• m dòng cuối cùng, mỗi dòng chứa hai số nguyên ~L, R~.

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

Ví dụ:

Input

3
1 2 3
3
1 2
2 3
3 3

Output

3
5
3

Giới hạn: 1 ≤ n, m ≤ ~10^5~; 0 <~a_1~, ~a_2~, …, ~a_n~ ≤ ~10^9~; 1 ≤ L ≤ R ≤ ~10^9~.

Ràng buộc:

• Subtask1: 40% số test ứng 40% số điểm của bài có n, m ≤ ~10^2~.
• Subtask2: 30% số test khác ứng 30% số điểm của bài có n, m ≤ ~10^3~
• Subtask3: 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì.