Cho một dãy $A_1, A_2, \ldots, A_N$ có độ dài $N$. Tất cả các số trong dãy đều nằm trong khoảng từ $1$ đến $N$ và đôi một khác nhau. Hãy viết chương trình xử lý các truy vấn sau:

• l r: đưa ra số lượng cặp số nguyên $(x, y)$ thỏa mãn $l \le x \le y \le r$ và $(max_{i=x}^{y} A_i) - (min_{i=x}^{y} A_i) = y - x$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$, độ dài của dãy. ($1 \le N \le 120{,}000$)

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$, đôi một khác nhau. ($1 \le A_i \le N$)

Dòng thứ ba chứa một số nguyên $M$, số lượng truy vấn. ($1 \le M \le 120{,}000$)

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn dạng l r. ($1 \le l \le r \le N$)

Dữ liệu ra

Với mỗi truy vấn, đưa ra một dòng chứa một số nguyên — kết quả.

Ví dụ

Dữ liệu vào 1

5
1 3 2 5 4
5
1 1
1 2
1 3
1 4
1 5

Dữ liệu ra 1

1
2
5
6
10