Dany jest ciąg $A_1, A_2, \ldots, A_N$ długości $N$. Wszystkie liczby w ciągu są z przedziału $1$ do $N$ i są parami różne. Napisz program przetwarzający następujące zapytania:

• l r: wypisz liczbę par całkowitych $(x, y)$ takich, że $l \le x \le y \le r$ oraz $(max_{i=x}^{y} A_i) - (min_{i=x}^{y} A_i) = y - x$.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $N$, długość ciągu. ($1 \le N \le 120\,000$)

Drugi wiersz zawiera $N$ liczb całkowitych $A_1, A_2, \ldots, A_N$, wszystkie różne. ($1 \le A_i \le N$)

Trzeci wiersz zawiera liczbę całkowitą $M$, liczbę zapytań. ($1 \le M \le 120\,000$)

Kolejne $M$ wierszy zawiera po jednym zapytaniu w formacie l r. ($1 \le l \le r \le N$)

Wyjście

Dla każdego zapytania wypisz wiersz zawierający jedną liczbę całkowitą – odpowiedź.

Przykład

Wejście 1

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

Wyjście 1

1
2
5
6
10