長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。数列の要素はすべて $1$ 以上 $N$ 以下であり、互いに相異なる。次のクエリを処理するプログラムを作成せよ。

• l r: 以下の条件を満たす整数の組 $(x, y)$ の個数を出力せよ：$l \le x \le y \le r$ かつ $(max_{i=x}^{y} A_i) - (min_{i=x}^{y} A_i) = y - x$.

入力

1 行目には整数 $N$ が含まれ、これは数列の長さを表す。（$1 \le N \le 120{,}000$）

2 行目には $N$ 個の整数 $A_1, A_2, \ldots, A_N$ が含まれる。これらはすべて相異なる。（$1 \le A_i \le N$）

3 行目には整数 $M$ が含まれ、これはクエリの個数を表す。（$1 \le M \le 120{,}000$）

続く $M$ 行の各行には、l r の形式でクエリが与えられる。（$1 \le l \le r \le N$）

出力

各クエリについて、答えを表す整数を 1 行に出力せよ。

入出力例

入力例 1

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

出力例 1

1
2
5
6
10