Soit une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$. Tous les nombres de la séquence sont compris entre $1$ et $N$ et sont deux à deux distincts. Écrire un programme pour traiter les requêtes suivantes :

• l r : afficher le nombre de paires d'entiers $(x, y)$ telles que $l \le x \le y \le r$ et $(\max_{i=x}^{y} A_i) - (\min_{i=x}^{y} A_i) = y - x$.

Entrée

La première ligne contient un entier $N$, la longueur de la séquence. ($1 \le N \le 120\,000$)

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_N$, tous distincts. ($1 \le A_i \le N$)

La troisième ligne contient un entier $M$, le nombre de requêtes. ($1 \le M \le 120\,000$)

Les $M$ lignes suivantes contiennent chacune une requête au format l r. ($1 \le l \le r \le N$)

Sortie

Pour chaque requête, afficher une ligne contenant un entier — la réponse.

Exemples

Entrée 1

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

Sortie 1

1
2
5
6
10