给定一个排列 $A = (A_1, A_2, \dots, A_N)$，它是 $(1, 2, \dots, N)$ 的一个排列。 对于一对整数 $l, r$ ($1 \le l \le r \le N$)，我们定义笛卡尔树 $C(l, r)$ 如下：

• $C(l, r)$ 是一棵包含 $r - l + 1$ 个节点的有根二叉树。我们将这棵树的根节点记为 $rt$。
• 令 $m$ 为满足 $A_m = \min\{A_l, A_{l+1}, \dots, A_r\}$ 的唯一整数。
• 如果 $l < m$，则 $rt$ 的左子树为 $C(l, m - 1)$。如果 $l = m$，则 $rt$ 没有左孩子。
• 如果 $m < r$，则 $rt$ 的右子树为 $C(m + 1, r)$。如果 $m = r$，则 $rt$ 没有右孩子。

给定 $Q$ 对整数 $(l_1, r_1), (l_2, r_2), \dots, (l_Q, r_Q)$。请确定在 $C(l_1, r_1), C(l_2, r_2), \dots, C(l_Q, r_Q)$ 中有多少个不同的笛卡尔树。

当且仅当满足以下所有条件时，两棵笛卡尔树 $X$ 和 $Y$ 被认为是相同的：

• 令 $X$ 的根为 $rt_X$，$Y$ 的根为 $rt_Y$。
• 如果 $rt_X$ 有左孩子，则 $rt_Y$ 也必须有左孩子，且 $rt_X$ 和 $rt_Y$ 的左子树是相同的笛卡尔树。
• 如果 $rt_X$ 没有左孩子，则 $rt_Y$ 也必须没有左孩子。
• 如果 $rt_X$ 有右孩子，则 $rt_Y$ 也必须有右孩子，且 $rt_X$ 和 $rt_Y$ 的右子树是相同的笛卡尔树。
• 如果 $rt_X$ 没有右孩子，则 $rt_Y$ 也必须没有右孩子。

输入格式

输入格式如下：

$N$ $A_1 \ A_2 \ \dots \ A_N$ $Q$ $l_1 \ r_1$ $l_2 \ r_2$ $\vdots$ $l_Q \ r_Q$

• 所有输入值均为整数。
• $1 \le N \le 4 \times 10^5$。
• $A$ 是 $(1, 2, \dots, N)$ 的一个排列。
• $1 \le Q \le 4 \times 10^5$。
• $1 \le l_i \le r_i \le N$ ($1 \le i \le Q$)。
• $(l_i, r_i) \neq (l_j, r_j)$ ($1 \le i < j \le Q$)。

输出格式

输出给定区间对 $(l_1, r_1), (l_2, r_2), \dots, (l_Q, r_Q)$ 中不同笛卡尔树的数量。

样例

样例输入 1

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

样例输出 1

2

样例输入 2

4
1 2 3 4
10
1 1
2 2
3 3
4 4
1 2
2 3
3 4
1 3
2 4
1 4

样例输出 2

4

样例输入 3

10
3 8 4 7 2 5 9 10 1 6
13
5 8
2 6
7 9
3 8
3 5
2 4
4 6
1 9
3 7
6 9
2 10
4 9
3 9

样例输出 3

11

说明

在第一个样例中，$C(1, 4), C(2, 5), C(3, 6)$ 分别为以下笛卡尔树：

$C(1, 4)$ 和 $C(3, 6)$ 是相同的笛卡尔树，而 $C(2, 5)$ 与它们不同。因此，共有 2 个不同的笛卡尔树。