给定一个长度为 $N$ 的数列 $A_1, A_2, \ldots, A_N$。数列中的所有数都在 $1$ 到 $N$ 之间且互不相同。请编写一个程序处理以下查询：

• l r：输出满足 $l \le x \le y \le r$ 且 $(max_{i=x}^{y} A_i) - (min_{i=x}^{y} A_i) = y - x$ 的整数对 $(x, y)$ 的个数。

输入格式

第一行包含一个整数 $N$，表示数列的长度。($1 \le N \le 120{,}000$)

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，所有数互不相同。($1 \le A_i \le N$)

第三行包含一个整数 $M$，表示查询的个数。($1 \le M \le 120{,}000$)

接下来 $M$ 行，每行给出一个查询，格式为 l r。($1 \le l \le r \le N$)

输出格式

对于每个查询，输出一行一个整数表示答案。

样例

输入格式 1

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

输出格式 1

1
2
5
6
10