E. 好子段

时间限制：7 秒
内存限制：512 MB

一个长度为 $n$ 的排列 $p$ 是一个序列 $p_1, p_2, \dots, p_n$，包含 $n$ 个不同的整数，每个整数都在 $1$ 到 $n$ 之间（$1 \le p_i \le n$）。

如果子段 $[l, r]$ 的最小值到最大值之间的所有整数都出现在 $p_l, p_{l+1}, \dots, p_r$ 中，则称该子段是好的。

例如，排列 $[1,3,2,5,4]$ 的好子段有：

$[1,1]$、$[1,3]$、$[1,5]$、$[2,2]$、$[2,3]$、$[2,5]$、$[3,3]$、$[4,4]$、$[4,5]$、$[5,5]$。

现在给你一个排列 $p_1, p_2, \dots, p_n$。

你需要回答 $q$ 个查询，每个查询的形式为：给定排列的一个子段 $[l, r]$，求该子段内有多少个好子段。

换句话说，对于一个查询 $[l, r]$，你需要统计满足 $l \le x \le y \le r$ 且子段 $[x, y]$ 是好子段的个数。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 120000$）—— 排列的长度。

第二行包含 $n$ 个用空格隔开的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$），它们构成一个排列。

第三行包含一个整数 $q$（$1 \le q \le 120000$）—— 查询的数量。

接下来 $q$ 行，每行包含两个整数 $l, r$（$1 \le l \le r \le n$），表示一个查询。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个查询对应的好子段数量。

示例

输入

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

输出

1
2
5
6
10
1
3
4
7
1
2
4
1
3
1